Site icon

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

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

Fig 1: Level of node in binary tree

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

No.Binary Tree Node (s) Level
1A 0
2B, C 1
3D, E, F, G 2
4H, I 3
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.
Fig 2: Level of each node in binary 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

 

Exit mobile version