Site icon

Check leaf nodes of binary tree are at same level – BFS / example

Fig 1: Node’s level – binary tree

Example 1:  Given a binary tree (Fig 2), Check whether leaf nodes are at same level.

Fig 2: Leaf nodes at same level

S. No.Leaf Node Level
1D 2
2E 2
3F 2
4G 2
We have discussed similar the problem Find Max width of a binary tree . Let us discuss the breadth first search algorithm to check whether leaf nodes are at same level.

Example 2: Check level of leaf nodes in a given binary tree (Fig 3)

Fig 3: Leaf nodes at different level

We will follow the similar algorithm for current example and we will find out level of each leaf node.
Time complexity:  O(n).
Let us look into the complete code as follows:
1.) IsLeafAtSameLevel Class: IsLeafAtSameLevel class is used to check whether leaf nodes of binary tree are at same level using breadth first search recursive algorithm.

package org.learn.Question;

import java.util.LinkedList;
import java.util.Queue;

public class IsLeavesAtSameLevel {
	public static boolean isLeavesAtSameLevel(Node root) {
		if (root == null) {
			System.out.println("Tree is empty");
			return false;
		}
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		// level delimiter
		queue.offer(null);
		int level = 0;
		boolean bLeafFound = false;
		int leafLevel = -1;

		while (!queue.isEmpty()) {
			Node node = queue.poll();
			// Level change
			if (null == node) {
				if (!queue.isEmpty()) {
					// level delimiter
					queue.offer(null);
				}
				level++;
			} else {
				if (node.left == null && node.right == null) {
					// first leaf found
					if (bLeafFound == false) {
						bLeafFound = true;
						leafLevel = level;
					} else { // Leaves are at different level
						if (leafLevel != level) {
							return false;
						}
					}
				}
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
		return true;
	}
}

2.) Node Class: Node class representing the nodes of a binary tree.  Node class has following attributes

package org.learn.Question;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}

	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class : We are creating the binary tree in main function & we are calling IsLeafAtSameLevel class, to find out whether leaf nodes are at same level using level order traversal.

package org.learn.Client;

import org.learn.Question.IsLeavesAtSameLevel;
import org.learn.Question.Node;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(50);
       //Level 1
       Node B = Node.createNode(25);
       Node C = Node.createNode(75);
       //Level 2
       Node D = Node.createNode(10);
       Node E = Node.createNode(30);
       Node F = Node.createNode(60);
       Node G = Node.createNode(80);
       //Level 3
       Node H = Node.createNode(55);
       Node I = Node.createNode(65);
             
       //connect Level 0 and 1
       A.left = B;
       A.right = C;
       //connect level 1 and level 2
       B.left = D;
       B.right = E;
       C.left = F;
       C.right = G;
       
       boolean isLeafAtSameLevel = IsLeavesAtSameLevel.isLeavesAtSameLevel(A);      
       if(isLeafAtSameLevel) {
    	   System.out.println("1. Leaf nodes of binary tree are at same level");
       } else {
    	   System.out.println("1. Leaf nodes of binary tree are not at same level");
       }
       
       //Connect level 2 and level 3
       F.left = H;
       F.right = I; 
       isLeafAtSameLevel = IsLeavesAtSameLevel.isLeavesAtSameLevel(A);      
       if(isLeafAtSameLevel) {
    	   System.out.println("2. Leaf nodes of binary tree are at same level");
       } else {
    	   System.out.println("2. Leaf nodes of binary tree are not at same level");
       }
    }
}

The output of main function [Fig 2 and Fig 3] is as follows:

1. Leaf nodes of binary tree are at same level
2. Leaf nodes of binary tree are not at same level

Download Code – Level of leaf node in binary tree (BFS)

 

Exit mobile version