C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML
Q. Program to determine whether all leaves are at same level.ExplanationIn 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
SolutionPython#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 JAVApublic 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
Next TopicPrograms List
|