Check whether a given binary tree is perfect or not

Example of perfect binary tree

Here given code implementation process.

/*
  C Program 
+ Check whether a given binary tree is perfect or not
*/
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Tree node
struct Node
{
  int data;
  struct Node*left,*right;
};

//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes

struct Node* insert(int data)
{
  //create dynamic memory to new binary tree node
  struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));
  if(new_node!=NULL)
  {
    //set data and pointer values
    new_node->data=data;
    new_node->left=NULL; //Initially node left-pointer is NULL
    new_node->right=NULL;//Initially node right-pointer is NULL
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;
  
}
//Find the status of given binary tree is perfect or not
int perfect_bt(struct Node*root,int *height,int level)
{
  if(root!=NULL)
  {
    if(root->left!=NULL 
      && root->right ==NULL 
      || root->left==NULL 
      && root->right !=NULL)
    {
      return 0;
    }

    return (perfect_bt(root->left,height,level+1) && 
            perfect_bt(root->right,height,level+1) );
  
  }else
  {
    if(*height==-1)
    {
      *height=level-1;
    }
    else if(level-1!=*height)
    {
      //WHEN leaf node are not same
      return 0;
    }
    return 1;
    
  }
}

void inorder(struct Node*head)
{
  if(head!=NULL)
  {
    inorder(head->left);
    printf("  %d",head->data);
    inorder(head->right);
  }
}
int main(){

  struct Node*root=NULL;

  /*  Make A Binary Tree
  -----------------------
           1
         /   \
        2     4
       / \   / \
      3   7 6   5
     
              
  */
  //Insertion of binary tree nodes
  root               =insert(1);
  root->left         =insert(2);
  root->left->left   =insert(3);

  root->right        =insert(4);
  root->right->right =insert(5);
  root->right->left  =insert(6);
  root->left->right   =insert(7);


  int height=-1,result=0;
  inorder(root);

  result=perfect_bt(root,&height,0);

  if(result==1)
  {
    printf("\n Perfect BT\n");
  }
  else
  {
    printf("\n Not Perfect BT\n");
  }
  return 0;
}

Output

  3  2  7  1  6  4  5
 Perfect BT
/*
C++ Program 
Check whether a given binary tree is perfect or not
*/
#include <iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left, *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinaryTree {
public:
  Node *root;
  int height;
  BinaryTree() {
    this->root = NULL;
    this->height = -1;
  }
  void inorder(Node *node) {
    if (node != NULL) {
      this->inorder(node->left);
      cout << "  " << node->data;
      this->inorder(node->right);
    }
  }
  bool is_perfect_bt(Node *head, int level) {
    if (head != NULL) {
      if (head->left != NULL && head->right == NULL || head->left == NULL && head->right != NULL) {
        return false;
      }
      return (this->is_perfect_bt(head->left, level + 1) && this->is_perfect_bt(head->right, level + 1));
    } else {
      if (this->height == -1) {
        this->height = level - 1;
      } else
      if (level - 1 != this->height) {
        return false;
      }
      return true;
    }
  }
  bool perfect_bt() {
    this->height = -1;
    return this->is_perfect_bt(this->root, 0);
  }
};

int main() {
  BinaryTree obj;
  /*  Make A Binary Tree
  -----------------------
           1
         /   \
        2     4
       / \   / \
      3   7 6   5
     
              
  */
  obj.root = new Node(1);
  obj.root->left = new Node(2);
  obj.root->left->left = new Node(3);
  obj.root->right = new Node(4);
  obj.root->right->right = new Node(5);
  obj.root->right->left = new Node(6);
  obj.root->left->right = new Node(7);
  obj.inorder(obj.root);
  if (obj.perfect_bt() == true) {
    cout << "\n Perfect BT\n";
  } else {
    cout << "\n Not Perfect BT\n";
  }
  return 0;
}

Output

  3  2  7  1  6  4  5
 Perfect BT
/*
Java Program 
Check whether a given binary tree is perfect or not
*/

//Class of Binary Tree node
class Node {

  public int data;
  public Node left, right;
  //Make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = null;
    right = null;
  }
}

public class BinaryTree {

  public Node root;

  public int height;

  public BinaryTree() {
    //Set initial initial values
    root = null;
    height = -1;
  }
  //Display tree element inorder form
  public void inorder(Node node) {

    if (node != null) {

      inorder(node.left);
      //Print node value
      System.out.print("  " + node.data);
      inorder(node.right);
    }
  }
  //Find the status of given binary tree is perfect or not
  public boolean is_perfect_bt(Node head, int level) {
    if (head != null) {
      if (head.left != null &&
        head.right == null ||
        head.left == null &&
        head.right != null) {
        return false;
      }
       
      return (is_perfect_bt(head.left, level + 1) &&
        is_perfect_bt(head.right, level + 1));

    } else {
      if (height == -1) {
        height = level - 1;
      } else if (level - 1 != height) {
        //WHEN leaf node are not same
        return false;
      }
      return true;

    }
  }
  public boolean perfect_bt() {
    this.height = -1;

    return is_perfect_bt(root, 0);
  }
  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();
    /* Make A Binary Tree
    -----------------------
             1
           /   \
          2     4
         / \   / \
        3   7 6   5
       
                
    */
    //Binary tree nodes
    obj.root = new Node(1);
    obj.root.left = new Node(2);
    obj.root.left.left = new Node(3);

    obj.root.right = new Node(4);
    obj.root.right.right = new Node(5);
    obj.root.right.left = new Node(6);
    obj.root.left.right = new Node(7);
    obj.inorder(obj.root);
    if (obj.perfect_bt()==true) {
      System.out.print("\n Perfect BT\n");
    } else {
      System.out.print("\n Not Perfect BT\n");
    }

  }
}

Output

  3  2  7  1  6  4  5
 Perfect BT
/*
C# Program 
Check whether a given binary tree is perfect or not
*/
using System;
//Class of Binary Tree node
public class Node {

	public int data;
	public Node left, right;
	//Make a tree node
	public Node(int value) {
		//Assign field values
		data = value;
		left = null;
		right = null;
	}
}

public class BinaryTree {

	public Node root;

	public int height;

	public BinaryTree() {
		//Set initial initial values
		root = null;
		height = -1;
	}
	//Display tree element inorder form
	public void inorder(Node node) {

		if (node != null) {

			inorder(node.left);
			//Print node value
			Console.Write("  " + node.data);
			inorder(node.right);
		}
	}
	//Find the status of given binary tree is perfect or not
	public Boolean is_perfect_bt(Node head, int level) {
		if (head != null) {
			if (head.left != null &&
				head.right == null ||
				head.left == null &&
				head.right != null) {
				return false;
			}

			return (is_perfect_bt(head.left, level + 1) &&
				is_perfect_bt(head.right, level + 1));

		} else {
			if (height == -1) {
				height = level - 1;
			} else if (level - 1 != height) {
				//WHEN leaf node are not same
				return false;
			}
			return true;

		}
	}
	public Boolean perfect_bt() {
		this.height = -1;

		return is_perfect_bt(root, 0);
	}
	public static void Main(String[] args) {
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();
		/* Make A Binary Tree
    -----------------------
             1
           /   \
          2     4
         / \   / \
        3   7 6   5
       
                
    */
		//Binary tree nodes
		obj.root = new Node(1);
		obj.root.left = new Node(2);
		obj.root.left.left = new Node(3);

		obj.root.right = new Node(4);
		obj.root.right.right = new Node(5);
		obj.root.right.left = new Node(6);
		obj.root.left.right = new Node(7);
		obj.inorder(obj.root);
		if (obj.perfect_bt()==true) {
			Console.Write("\n Perfect BT\n");
		} else {
			Console.Write("\n Not Perfect BT\n");
		}

	}
}

Output

  3  2  7  1  6  4  5
 Perfect BT
# Python Program 
# Check whether a given binary tree is perfect or not
class Node :
  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinaryTree :
  def __init__(self) :
    self.root = None
    self.height = -1
  
  def inorder(self, node) :
    if (node != None) :
      self.inorder(node.left)
      print(node.data,end=" ")
      self.inorder(node.right)
    
  
  def is_perfect_bt(self, head, level) :
    if (head != None) :
      if (head.left != None and head.right == None or head.left == None and head.right != None) :
        return False
      
      return (self.is_perfect_bt(head.left, level + 1) and self.is_perfect_bt(head.right, level + 1))
    
    else :
      if (self.height == -1) :
        self.height = level - 1
      elif (level - 1 != self.height) :
        return False
      
      return True
    
  
  def perfect_bt(self) :
    self.height = -1
    return self.is_perfect_bt(self.root, 0)
  
def main() :
  obj = BinaryTree()
  #  Make A Binary Tree
  #           1
  #         /   \
  #        2     4
  #       / \   / \
  #      3   7 6   5
  #   
  obj.root = Node(1)
  obj.root.left = Node(2)
  obj.root.left.left = Node(3)
  obj.root.right = Node(4)
  obj.root.right.right = Node(5)
  obj.root.right.left = Node(6)
  obj.root.left.right = Node(7)
  obj.inorder(obj.root)
  if (obj.perfect_bt() == True) :
    print("\n Perfect BT\n")
  else :
    print("\n Not Perfect BT\n")
    
  

if __name__ == "__main__":
  main()

Output

  3  2  7  1  6  4  5
 Perfect BT
# Ruby Program
# Check whether a given binary tree is perfect or not
class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinaryTree 
	attr_reader :root, :height
	attr_accessor :root, :height
	def initialize() 
		@root = nil
		@height = -1
	end
	def inorder(node) 
		if (node != nil) 
			self.inorder(node.left)
			print("  ", node.data)
			self.inorder(node.right)
		end
	end
	def is_perfect_bt(head, level) 
		if (head != nil) 
			if (head.left != nil and head.right == nil or head.left == nil and head.right != nil) 
				return false
			end
			return (self.is_perfect_bt(head.left, level + 1) and self.is_perfect_bt(head.right, level + 1))
		else 
			if (@height == -1) 
				@height = level - 1
			elsif (level - 1 != @height) 
				return false
			end
			return true
		end
	end
	def perfect_bt() 
		self.height = -1
		return self.is_perfect_bt(@root, 0)
	end
end

def main() 
	obj = BinaryTree.new()
	#  Make A Binary Tree
	#           1
	#         /   \
	#        2     4
	#       / \   / \
	#      3   7 6   5
	#   
	obj.root = Node.new(1)
	obj.root.left = Node.new(2)
	obj.root.left.left = Node.new(3)
	obj.root.right = Node.new(4)
	obj.root.right.right = Node.new(5)
	obj.root.right.left = Node.new(6)
	obj.root.left.right = Node.new(7)
	obj.inorder(obj.root)
	if (obj.perfect_bt() == true) 
		print("\n Perfect BT\n")
	else 
		print("\n Not Perfect BT\n")
	end
end
main()

Output

  3  2  7  1  6  4  5
 Perfect BT
<?php
/*
  Php Program
  Check whether a given binary tree is perfect or not
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinaryTree {
  public $root;
  public $height;

  function __construct() {
    $this->root = null;
    $this->height = -1;
  }
  public  function inorder($node) {
    if ($node != null) {
      $this->inorder($node->left);
      echo("  ". $node->data);
      $this->inorder($node->right);
    }
  }
  public  function is_perfect_bt($head, $level) {
    if ($head != null) {
      if ($head->left != null && $head->right == null || $head->left == null && $head->right != null) {
        return false;
      }
      return ($this->is_perfect_bt($head->left, $level + 1) && $this->is_perfect_bt($head->right, $level + 1));
    } else {
      if ($this->height == -1) {
        $this->height = $level - 1;
      } else
      if ($level - 1 != $this->height) {
        return false;
      }
      return true;
    }
  }
  public  function perfect_bt() {
    $this->height = -1;
    return $this->is_perfect_bt($this->root, 0);
  }
}

function main() {
  $obj = new BinaryTree();
  /*  Make A Binary Tree
  -----------------------
           1
         /   \
        2     4
       / \   / \
      3   7 6   5
     
              
  */
  $obj->root = new Node(1);
  $obj->root->left = new Node(2);
  $obj->root->left->left = new Node(3);
  $obj->root->right = new Node(4);
  $obj->root->right->right = new Node(5);
  $obj->root->right->left = new Node(6);
  $obj->root->left->right = new Node(7);
  $obj->inorder($obj->root);
  if ($obj->perfect_bt() == true) {
    echo("\n Perfect BT\n");
  } else {
    echo("\n Not Perfect BT\n");
  }
}
main();

Output

  3  2  7  1  6  4  5
 Perfect BT
/*
  Node JS Program
  Check whether a given binary tree is perfect or not
*/
class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree {
	
	constructor() {
		this.root = null;
		this.height = -1;
	}
	inorder(node) {
		if (node != null) {
			this.inorder(node.left);
			process.stdout.write("  " + node.data);
			this.inorder(node.right);
		}
	}
	is_perfect_bt(head, level) {
		if (head != null) {
			if (head.left != null && head.right == null || head.left == null && head.right != null) {
				return false;
			}
			return (this.is_perfect_bt(head.left, level + 1) && this.is_perfect_bt(head.right, level + 1));
		} else {
			if (this.height == -1) {
				this.height = level - 1;
			} else
			if (level - 1 != this.height) {
				return false;
			}
			return true;
		}
	}
	perfect_bt() {
		this.height = -1;
		return this.is_perfect_bt(this.root, 0);
	}
}

function main() {
	var obj = new BinaryTree();
	/*  Make A Binary Tree
    ---------------------
           1
         /   \
        2     4
       / \   / \
      3   7 6   5
     
              
   */
	obj.root = new Node(1);
	obj.root.left = new Node(2);
	obj.root.left.left = new Node(3);
	obj.root.right = new Node(4);
	obj.root.right.right = new Node(5);
	obj.root.right.left = new Node(6);
	obj.root.left.right = new Node(7);
	obj.inorder(obj.root);
	if (obj.perfect_bt() == true) {
		process.stdout.write("\n Perfect BT\n");
	} else {
		process.stdout.write("\n Not Perfect BT\n");
	}
}
main();

Output

  3  2  7  1  6  4  5
 Perfect BT
/*
  Swift 4 Program
  Check whether a given binary tree is perfect or not
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
 
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinaryTree {
  var root: Node? ;
  var height: Int;
  init() {
    self.root = nil;
    self.height = -1;
  }
  func inorder(_ node: Node? ) {
    if (node != nil) {
      self.inorder(node!.left);
      print(node!.data, terminator:"  ");
      self.inorder(node!.right);
    }
  }
  func is_perfect_bt(_ head: Node? , _ level : Int) -> Bool {
    if (head != nil) {
      if (head!.left != nil && head!.right == nil || head!.left == nil && head!.right != nil) {
        return false;
      }
      return (self.is_perfect_bt(head!.left, level + 1) && self.is_perfect_bt(head!.right, level + 1));
    } else {
      if (self.height == -1) {
        self.height = level - 1;
      } else
      if (level - 1 != self.height) {
        return false;
      }
      return true;
    }
  }
  func perfect_bt() -> Bool {
    self.height = -1;
    return self.is_perfect_bt(self.root, 0);
  }
}
func main() {
  let obj: BinaryTree = BinaryTree();
  /*  Make A Binary Tree
    ---------------------
           1
         /   \
        2     4
       / \   / \
      3   7 6   5
     
              
  */
  obj.root = Node(1);
  obj.root!.left = Node(2);
  obj.root!.left!.left = Node(3);
  obj.root!.right = Node(4);
  obj.root!.right!.right = Node(5);
  obj.root!.right!.left = Node(6);
  obj.root!.left!.right = Node(7);
  obj.inorder(obj.root);
  if (obj.perfect_bt() == true) {
    print("\n Perfect BT\n");
  } else {
    print("\n Not Perfect BT\n");
  }
}
main();

Output

  3  2  7  1  6  4  5
 Perfect BT

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved