Find level of node in binary tree – BFS (non-recursive) & example

• Given a binary tree, find out the level of input node using non recursive algorithm.
• Traverse the binary tree using breadth first search  (BFS) or level order traversal algorithm.
• What is level in a binary tree?
  • Level is distance or hops of node with respect to root node.
  • The root node is considered to be at level 0 & immediate children of root node is at level 1 (level of root node + 1).
  • Calculate the level of all the nodes in a binary tree (wrt level of its parent node).

The root node A is at level 0 and its children B and C is at level 1 (refer Fig 1)

The level of nodes in a binary tree are as follows:

Let us look into the BFS algorithm, to find the level of input node. We will tweak the BFS algorithm to keep track of  level of node.

• Insert root to queue.
• Insert null to the queue (delimiter to know that we have finished the current level)
• Iterate through the Queue
  • Pop node from queue
  • Check node is null [The delimiter added earlier]
    • We are at next level and Increment the level.
  • Compare the popped up node with input node [data]
    • If this the node we are looking for.
      • We got the level, break from the loop
  • Add next level children (left and right child)
• Once we exit the loop, we will know the level of input node (if found in tree).

Let us go through the complete code, to find out the level of input node using level order traversal or breadth first search non recursive algorithm as follows:
1.) LevelOfNodeInBTree Class: LevelOfNodeInBTree is used to find the level of node using breadth first search algorithm in a binary tree.

package org.learn.Question;

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

public class LevelOfNodeInBTree {
	public static void  levelOfNodeInBTree(Node root, Node inputNode) {
		if (root == null) {
			System.out.println("Tree is empty");
			return ;
		}
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		//level delimiter
		queue.offer(null);
		int level = 0;
		boolean found = false;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			//Level change
			if (null == node) {
				if (!queue.isEmpty()) {
					//level delimiter
					queue.offer(null);
				}	
				level ++;
			} else {
				if( inputNode.data == node.data) {
					found = true;
					break;
				}
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
		if(found) {
			System.out.printf("Found data %d at level %d \n",inputNode.data,level);
		} else {
			System.out.printf("Node could not found in binary tree");			
		}
		
		return;
	}
}

2.) Node Class: The class representing the nodes of a binary tree.

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 a main method & Calling LevelOfNodeInBTree class ,to find the level of input node in a binary tree using level order traversal algorithm.

package org.learn.Client;

import org.learn.Question.LevelOfNodeInBTree;
import org.learn.Question.Node;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
             
       //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;
       //Connect level 2 and level 3
       F.left = H;
       F.right = I;       
       
       //Pass root node and input node
       LevelOfNodeInBTree.levelOfNodeInBTree(A,A);      
       LevelOfNodeInBTree.levelOfNodeInBTree(A,C);  
       LevelOfNodeInBTree.levelOfNodeInBTree(A,F);      
       LevelOfNodeInBTree.levelOfNodeInBTree(A,H);   
    }
}

The output of main function is as follows:

Found data 100 at level 0
Found data 150 at level 1
Found data 125 at level 2
Found data 120 at level 3

Download Code–Level of node in binary tree non-recursive