Check if all leaves are at same level

Suppose that given binary tree are contains N nodes. Check if programmatically, on this binary tree all leaf nodes are exist in a same level. for example.

Check if all leaves are at same level

Here given code implementation process.

/*
  C Program 
+ Check if all leaves are at same level
*/
#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;
  
}
//Check Leaf nodes are at same level
void check_Leaf_level(struct Node*node,int height,int *status){

  if(node!=NULL && *status!=-1){

    check_Leaf_level(node->left,height+1,status);

    if(node->left==NULL && node->right==NULL && height){
      //that is an leaf node
      if(*status==0){
        //When first leaf node
        *status=height;
      }else if(*status!=height){
        *status=-1;
      }
    }
    check_Leaf_level(node->right,height+1,status);
  }
}


int main(){

  struct Node*root=NULL;
  int status=0;
  /*  Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
  */
  //Insertion of binary tree nodes
  root               =insert(1);
  root->left         =insert(2);
  root->right        =insert(3);
  root->right->right =insert(6);
  root->right->left  =insert(5);
  root->left->left   =insert(4);

  //Check Leaf Level
  check_Leaf_level(root,0,&status);
  
  if(root==NULL){
    printf("Empty linked list\n");
  }
  else if(status==-1){
    printf("No\n");
  }else{
    printf("Yes\n");
  }

    /*  Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
     /
    7  
  */

  //Add new node
  root->left->left->left  =insert(7);
  
  status=0;
  //Check new tree elements level
  check_Leaf_level(root,0,&status);
  if(root==NULL){
    printf("Empty linked list\n");
  }
  else if(status==-1){
    printf("No \n");
  }else{
    printf("Yes \n");
  }
  return 0;
}

Output

Yes
No 

/*
  C++ Program 
+ Check if all leaves are at same level
*/
#include<iostream>
using namespace std;

//Structure of Binary Tree node
class Node{
  public:
    int data;
    Node*left,*right;
    //make a tree node
    Node(int data){
      //assign field values
      this->data=data;
      left=right=NULL;
    }
};

class BinaryTree{
  public:
    Node*root;
    BinaryTree();
    void check_Leaf_level(Node*,int,int*);
};

//set initial tree root to NULL
BinaryTree:: BinaryTree(){
  root=NULL;
}

//Check Leaf nodes are at same level
void BinaryTree::check_Leaf_level(struct Node*node,int height,int *status){

  if(node!=NULL && *status!=-1){

    check_Leaf_level(node->left,height+1,status);

    if(node->left==NULL && node->right==NULL && height){
      //that is an leaf node
      if(*status==0){
        //When first leaf node
        *status=height;
      }else if(*status!=height){
        *status=-1;
      }
    }
    check_Leaf_level(node->right,height+1,status);
  }
}

int main(){

  BinaryTree obj;
  int status=0;
  /*  Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
  */
  //insertion of binary Tree nodes
  obj.root               =new Node(1);
  obj.root->left         =new Node(2);
  obj.root->right        =new Node(3);
  obj.root->right->right =new Node(6);
  obj.root->right->left  =new Node(5);
  obj.root->left->left   =new Node(4);


  obj.check_Leaf_level(obj.root,0,&status);

  if(obj.root==NULL){
    cout<<("Empty linked list\n");
  }
  else if(status==-1){
    cout<<("No\n");
  }else{
    cout<<("Yes\n");
  }

   //Add new node
  obj.root->left->left->left  =new Node(7);
  /*  When add new node
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
     /
    7  
  */
  status=0;
  obj.check_Leaf_level(obj.root,0,&status);

  if(obj.root==NULL){
    cout<<("Empty linked list\n");
  }
  else if(status==-1){
    cout<<("No\n");
  }else{
    cout<<("Yes\n");
  }
  return 0;
}

Output

Yes
No

/*
  Java Program 
  Check if all leaves are at same level
  
*/

//Class of Binary Tree node
class Node{

  int data;
  Node left, right;
  //make a tree node
  public Node(int data){
    //assign field values
    this.data=data;
    left=right=null;
  }
};

class BinaryTree{

    public Node root;
    public int status;

    public BinaryTree(){
    //set initial tree root to null
      root=null;
      status=0;
    }
  //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);
      }

    }
    //Check Leaf nodes are at same level
    public void checkLeafLevel(Node node,int height){

      if(node!=null &&  status!=-1){

        checkLeafLevel(node.left,height+1);

        if(node.left==null && node.right==null && height>0){
          //that is an leaf node
          if(status==0){
            //When first leaf node
             status=height;
          }else if(status!=height){
             status=-1;
          }
        }
        checkLeafLevel(node.right,height+1);
      }
    }

    public static void main(String[] args){
    //Make object of Binary Tree
      BinaryTree obj=new BinaryTree();

     
      /*   Make A Binary Tree
      -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
       */
      //insertion of binary Tree nodes
      obj.root             =new Node(1);
      obj.root.left        =new Node(2);
      obj.root.right       =new Node(3);
      obj.root.right.right =new Node(6);
      obj.root.right.left  =new Node(5);
      obj.root.left.left   =new Node(4);


      obj.checkLeafLevel(obj.root,0);

      if(obj.root==null){
        System.out.println("Empty linked list");
      }
      else if(obj.status==-1){
        System.out.println("No");
      }else{
        System.out.println("Yes");
      }

    //Add new node
      obj.root.left.left.left  =new Node(7);
      /*   When add new node
      -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
         /
        7  
       */
    obj.status=0;
    obj.checkLeafLevel(obj.root,0);

    if(obj.root==null){
      System.out.println("Empty linked list");
    }
    else if(obj.status==-1){
      System.out.println("No");
    }else{
      System.out.println("Yes");
    }
    
  }
}

Output

Yes
No
#Python Program 
#Check if all leaves are at same level
#using recursion
 
class Node:
    def __init__(self,data):
      #Assign node value
      self.data=data
      self.left,self.right=None,None


class BinaryTree:

    def __init__(self):
      #set initial tree root to None
      self.root=None
      self.status=0

    #Display tree element inorder form
    def inorder(self,node):
        if(node!=None):
            self.inorder(node.left)
            #Print node value
            print(node.data,end="  ")
            self.inorder(node.right)

    #Check Leaf nodes are at same level
    def checkLeafLevel(self,node,height):

      if(node!=None and  self.status!=-1):

        self.checkLeafLevel(node.left,height+1)

        if(node.left==None and node.right==None ):
          #that is an leaf node
          if(self.status==0):
            #When first leaf node
            self.status=height
          elif(self.status!=height):
            self.status=-1
        self.checkLeafLevel(node.right,height+1)
      
    
def main():
  #Make object of Binary Tree
  obj=BinaryTree()

  #   Make A Binary Tree
  #-----------------------
  #        1
  #       /  \
  #      2    3
  #     /    /  \
  #    4    5    6
  #
  #insertion of binary Tree nodes
  obj.root = Node(1)
  obj.root.left  = Node(2)
  obj.root.right = Node(3)
  obj.root.right.right = Node(6)
  obj.root.right.left =  Node(5)
  obj.root.left.left =  Node(4)

  obj.checkLeafLevel(obj.root,0)

  if(obj.root==None):
    print("Empty linked list")
  elif(obj.status==-1):
    print("No")
  else:
    print("Yes")


  #Add new node
  obj.root.left.left.left  = Node(7)
  #   When add new node 7
  #-----------------------
  #        1
  #       /  \
  #      2    3
  #     /    /  \
  #    4    5    6
  #   /
  #  7
  obj.status=0
  obj.checkLeafLevel(obj.root,0)

  if(obj.root==None):
    print("Empty linked list")
  elif(obj.status==-1):
    print("No")
  else:
  	print("Yes")
if __name__=="__main__":
  main()

Output

Yes
No

/* 
  C# Program 
  Check if all leaves are at same level
  //using recursion
 */
using System;
class Node{

	public int data;
	public Node left, right;
	//Make a tree node
	public Node(int data){
		//Assign fields values
		this.data=data;
		left=right=null;
	}
};
class BinaryTree
{
	public Node root;
	public int status=0;

	public BinaryTree(){
		//set initial tree root to null
		root = null;
	}
	//Check Leaf nodes are at same level
	public void checkLeafLevel(Node node,int height){

		if(node!=null &&  status!=-1){

			checkLeafLevel(node.left,height+1);

			if(node.left==null && node.right==null && height>0){
				//that is an leaf node
				if(status==0){
					//When first leaf node
					status=height;
				}else if(status!=height){
					status=-1;
				}
			}
			checkLeafLevel(node.right,height+1);
		}
	}

	static void Main()
	{
		//Make object of Binary Tree
		BinaryTree obj=new BinaryTree();


		/*   Make A Binary Tree
      -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
       */
		//insertion of binary Tree nodes
		obj.root             =new Node(1);
		obj.root.left        =new Node(2);
		obj.root.right       =new Node(3);
		obj.root.right.right =new Node(6);
		obj.root.right.left  =new Node(5);
		obj.root.left.left   =new Node(4);


		obj.checkLeafLevel(obj.root,0);

		if(obj.root==null){
			Console.WriteLine("Empty linked list");
		}
		else if(obj.status==-1){
			Console.WriteLine("No");
		}else{
			Console.WriteLine("Yes");
		}

		//Add new node
		obj.root.left.left.left  =new Node(7);
		/*   When add new node
      -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
         /
        7  
       */
		obj.status=0;
		obj.checkLeafLevel(obj.root,0);

		if(obj.root==null){
			Console.WriteLine("Empty linked list");
		}
		else if(obj.status==-1){
			Console.Write("No");
		}else{
			Console.WriteLine("Yes");
		}

	}
}

Output

Yes
No
<?php
//Php program 
//Check if all leaves are at same level
//using recursion
class Node
{
    public $data;
    public $left;
    public $right;

    function __construct($data)
    {
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTree{
	public $status;
    public $root;
    function __construct()
    {
      //set initial tree root to null
      $this->root=NULL;
      $this->status=0;
    }
    
    //Check Leaf nodes are at same level
	public function check_Leaf_level($node,$height){

	  if($node!=NULL && $this->status!=-1){

	    $this->check_Leaf_level($node->left,$height+1);

	    if($node->left==NULL && $node->right==NULL && $height>0){
	      //that is an leaf node
	      if($this->status==0){
	        //When first leaf node
	        $this->status=$height;
	      }else if($this->status!=$height){
	        $this->status=-1;
	      }
	    }
	    $this->check_Leaf_level($node->right,$height+1);
	  }
	}
}
function main(){
    //Make object of Binary Tree
    $obj=new BinaryTree();

    /*   Make A Binary Tree
      -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
       */
    //insertion of binary Tree nodes
    $obj->root                = new Node(1);
    $obj->root->left          = new Node(2);
    $obj->root->right         = new Node(3);
    $obj->root->right->right  = new Node(6);
    $obj->root->right->left   = new Node(5);
    $obj->root->left->left    = new Node(4);

  //Check Leaf Level
  $obj->check_Leaf_level($obj->root,0);
  
  if($obj->root==NULL){
    echo ("Empty linked list\n");
  }
  else if($obj->status==-1){
    echo ("No\n");
  }else{
    echo ("Yes \n");
  }

    /*  Make A Binary Tree
  -----------------------
          1
         /  \
        2    3
       /    /  \
      4    5    6
     /
    7  
  */

  //Add new node
  $obj->root->left->left->left  = new Node(7);
  
  $obj->status=0;
  //Check new tree elements level
  $obj->check_Leaf_level($obj->root,0);
  if($obj->root==NULL){
    echo ("Empty linked list\n");
  }
  else if($obj->status==-1){
    echo ("No \n");
  }else{
    echo ("Yes \n");
  }
}
main();
?>

Output

Yes
No

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