Q:

Program to determine whether all leaves are at same level

belongs to collection: Tree Programs

robaa
Save to bookmark
|
2022-11-09
|
  175 
0

Explanation

In this program, we need to check whether all the leaves of the given binary tree are at same level or not.

A Node is said to be leaf if it doesn't have any child node. In the below diagram, nodes 4, 5 and 6 are leaf nodes as they don't have any child node. Nodes 4, 5 and 6 are present at the same level, i.e., Level 2.

Algorithm

  1. Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
  3. Define another class which has two attribute root and level.
    1. Root represents the root node of the tree and initializes it to null.
    2. The level will be used to store the level of the first encountered leaf node.
  4. isSameLevel() will check whether all leaves of given binary tree are at same level or not:
    1. It checks whether the root is null, which means the tree is empty.
    2. If the tree is not empty, traverse through the tree and check for leaf node whose left and right children are null.
    3. CurrentLevel will keep track of current level being traversed.
    4. When the first leaf node is encountered, store the value of currentLevel in variable level.
    5. Traverse recursively through all level, check for subsequent leaf nodes. If currentLevel of all leaf is equal to the value stored in level then, all leaves are at same level.

Input:

Output:

All leaves are at same level
Python programming, Php programming, Java programming, C programming, c# programming, examples, Python programming examples, Php programming examples, Java programming examples, C programming examples, c# programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-09
need an explanation for this answer? contact us directly to get an explanation for this answer

Python

#Represent a node of binary tree  
class Node:  
    def __init__(self,data):  
        #Assign data to the new node, set left and right children to None  
        self.data = data;  
        self.left = None;  
        self.right = None;  
   
class LeafLevel:  
    def __init__(self):  
        #Represent the root of binary tree  
        self.root = None;  
        #It will store level of first encountered leaf   
        self.level = 0;  
          
    #isSameLevel() will check whether all leaves of the binary tree is at same level or not  
    def isSameLevel(self, temp, currentLevel):  
          
        #Check whether tree is empty  
        if(self.root == None):  
            print("Tree is empty");  
            return true;  
              
        else:  
            #Checks whether node is None  
            if(temp == None):  
                return True;  
                  
            if(temp.left == None and temp.right == None):  
                #If first leaf is encountered, set level to current level  
                if(self.level == 0):  
                    self.level = currentLevel;  
                    return True;  
                      
                #Checks whether the other leaves are at the same level as that of the first leaf  
                else:  
                    return (self.level == currentLevel);  
                      
            #Checks for leaf node in left and right subtree recursively.  
            return  (self.isSameLevel(temp.left, currentLevel + 1) and self.isSameLevel(temp.right, currentLevel + 1));  
                  
bt = LeafLevel();  
#Add nodes to the binary tree  
bt.root = Node(1);  
bt.root.left = Node(2);  
bt.root.right = Node(3);  
bt.root.left.left = Node(4);  
bt.root.right.left = Node(5);  
bt.root.right.right = Node(6);  
   
#Checks whether all leaves of given binary tree is at same level  
if(bt.isSameLevel(bt.root, 1)):  
    print("All leaves are at same level");  
else:  
    print("All leaves are not at same level");

 

Output:

All leaves are at same level

 

C

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  
   
//Represent a node of binary tree  
struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};  
   
//Represent the root of binary tree  
struct node *root = NULL;  
   
//It will store level of first encountered leaf   
static int level = 0;  
      
//createNode() will create a new node  
struct node* createNode(int data){  
    //Create a new node  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));  
    //Assign data to newNode, set left and right children to NULL  
    newNode->data= data;  
    newNode->left = NULL;  
    newNode->right = NULL;  
      
    return newNode;  
}  
   
//isSameLevel() will check whether all leaves of the binary tree is at the same level or not  
bool isSameLevel(struct node *temp, int currentLevel ) {  
      
    //Check whether tree is empty  
    if(root == NULL){  
        printf("Tree is empty\n");  
        return true;  
    }  
    else {  
        //Checks whether node is null  
        if(temp == NULL)  
            return true;  
   
        if(temp->left == NULL && temp->right == NULL) {  
            //If first leaf is encountered, set level to current level  
            if(level == 0) {  
                level = currentLevel ;  
                return true;  
            }  
            //Checks whether the other leaves are at the same level of that of first leaf  
            else   
               return (level == currentLevel) ;  
         }  
          
        //Checks for leaf node in left and right subtree recursively.  
        return  (isSameLevel(temp->left, currentLevel + 1) && isSameLevel(temp->right, currentLevel + 1)) ;  
     }  
}  
   
int main()  
{  
    //Add nodes to the binary tree  
    root = createNode(1);  
    root->left = createNode(2);  
    root->right = createNode(3);  
    root->left->left = createNode(4);  
    root->right->left = createNode(5);  
    root->right->right = createNode(6);  
      
    //Checks whether all leaves of given binary tree is at same level  
    if(isSameLevel(root, 1))   
        printf("All leaves are at same level");  
    else  
        printf("All leaves are not at same level");  
   
    return 0;  
}

 

Output:

All leaves are at same level

 

JAVA

public class LeafLevel {  
      
    //Represent a node of binary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
          
        public Node(int data){  
            //Assign data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
            }  
        }  
      
    //Represent the root of binary tree  
    public Node root;  
      
    //It will store level of first encountered leaf   
    public static int level = 0;  
    
    public LeafLevel(){  
        root = null;  
    }  
    
    //isSameLevel() will check whether all leaves of the binary tree is at same level or not  
    public boolean isSameLevel(Node temp, int currentLevel ) {  
          
        //Check whether tree is empty  
        if(root == null){  
          System.out.println("Tree is empty");  
          return true;  
        }  
        else {  
            //Checks whether node is null  
            if(temp==null)  
                return true;  
   
            if(temp.left == null && temp.right == null) {  
                //If first leaf is encountered, set level to current level  
                if(level == 0) {  
                    level = currentLevel ;  
                    return true;  
                }  
                //Checks whether the other leaves are at same level of that of first leaf  
                else   
                   return (level == currentLevel) ;  
             }  
              
            //Checks for leaf node in left and right subtree recursively.  
            return  (isSameLevel(temp.left, currentLevel + 1) && isSameLevel(temp.right, currentLevel + 1)) ;  
         }  
    }  
    
    public static void main (String[] args) {  
          
        LeafLevel bt = new LeafLevel();  
        //Add nodes to the binary tree  
        bt.root = new Node(1);  
        bt.root.left = new Node(2);  
        bt.root.right = new Node(3);  
        bt.root.left.left = new Node(4);  
        bt.root.right.left = new Node(5);  
        bt.root.right.right = new Node(6);  
      
        //Checks whether all leaves of given binary tree is at same level  
        if(bt.isSameLevel(bt.root, 1))   
            System.out.println("All leaves are at same level");  
        else  
            System.out.println("All leaves are not at same level");  
  }  
}

 

Output:

All leaves are at same level

 

C#

using System;  
namespace Tree   
{                       
    public class Program  
    {  
        //Represent a node of binary tree  
        public class Node<T>{  
            public T data;  
            public Node<T> left;  
            public Node<T> right;  
              
            public Node(T data) {  
                //Assign data to the new node, set left and right children to null  
                this.data = data;  
                this.left = null;  
                this.right = null;  
            }  
        }  
          
        public class LeafLevel<T>{  
            //Represent the root of binary tree  
            public Node<T> root;  
              
            //It will store level of first encountered leaf   
            public static int level = 0;  
              
            public LeafLevel(){  
                root = null;  
            }  
          
            //isSameLevel() will check whether all leaves of the binary tree is at same level or not  
            public Boolean isSameLevel(Node<int> temp, int currentLevel ) {  
   
                //Check whether tree is empty  
                if(root == null){  
                  Console.WriteLine("Tree is empty");  
                  return true;  
                }  
                else {  
                    //Checks whether node is null  
                    if(temp==null)  
                        return true;  
   
                    if(temp.left == null && temp.right == null) {  
                        //If first leaf is encountered, set level to current level  
                        if(level == 0) {  
                            level = currentLevel ;  
                            return true;  
                        }  
                        //Checks whether the other leaves are at same level of that of first leaf  
                        else   
                           return (level == currentLevel) ;  
                     }  
   
                    //Checks for leaf node in left and right subtree recursively.  
                    return  (isSameLevel(temp.left, currentLevel + 1) && isSameLevel(temp.right, currentLevel + 1)) ;  
                 }  
            }  
        }  
          
        public static void Main()  
        {  
            LeafLevel<int> bt = new LeafLevel<int>();  
            //Add nodes to the binary tree  
            bt.root = new Node<int>(1);  
            bt.root.left = new Node<int>(2);  
            bt.root.right = new Node<int>(3);  
            bt.root.left.left = new Node<int>(4);  
            bt.root.right.left = new Node<int>(5);  
            bt.root.right.right = new Node<int>(6);  
   
            //Checks whether all leaves of given binary tree is at same level  
            if(bt.isSameLevel(bt.root, 1))   
                Console.WriteLine("All leaves are at same level");  
            else  
                Console.WriteLine("All leaves are not at same level");                  
            }      
    }  
}

 

Output:

All leaves are at same level

 

PHP

<!DOCTYPE html>  
<html>  
<body>  
<?php  
//Represent a node of binary tree  
class Node{  
    public $data;  
    public $left;  
    public $right;  
      
    function __construct($data){  
        //Assign data to the new node, set left and right children to NULL  
        $this->data = $data;  
        $this->left = NULL;  
        $this->right = NULL;  
    }  
}  
class LeafLevel{  
    //Represent the root of binary tree  
    public $root;  
    //It will store level of first encountered leaf   
    public $level = 0;  
      
    function __construct(){  
        $this->root = NULL;  
        $this->level = 0;  
    }  
      
    //isSameLevel() will check whether all leaves of the binary tree is at same level or not  
    function isSameLevel($temp, $currentLevel ) {  
          
        //Check whether tree is empty  
        if($this->root == NULL){  
            print("Tree is empty <br>");  
              return true;  
        }  
        else {  
            //Checks whether node is null  
            if($temp == NULL)  
                return true;  
   
            if($temp->left == NULL && $temp->right == NULL) {  
                //If first leaf is encountered, set level to current level  
                if($this->level == 0) {  
                    $this->level = $currentLevel ;  
                    return true;  
                }  
                //Checks whether the other leaves are at same level of that of first leaf  
                else   
                   return ($this->level == $currentLevel) ;  
             }  
              
            //Checks for leaf node in left and right subtree recursively.  
            return  ($this->isSameLevel($temp->left, $currentLevel + 1) && $this->isSameLevel($temp->right, $currentLevel + 1)) ;  
         }  
    }  
}  
$bt = new LeafLevel();  
//Add nodes to the binary tree  
$bt->root= new Node(1);  
$bt->root->left = new Node(2);  
$bt->root->right = new Node(3);  
$bt->root->left->left = new Node(4);  
$bt->root->right->left = new Node(5);  
$bt->root->right->right = new Node(6);  
   
//Checks whether all leaves of given binary tree is at same level  
if($bt->isSameLevel($bt->root, 1))   
    print("All leaves are at same level");  
else  
    print("All leaves are not at same level");    
?>  
</body>  
</html>

 

Output:

All leaves are at same level

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Tree Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Program to determine whether two trees are identic... >>
<< Program to convert Binary Tree to Binary Search Tr...