Get Level/Height of node in binary tree

Get Level of node in Binary Tree. OR
Get Height of Node in Binary Tree.


Given a binary tree, you need to find the height of a given node in the tree.
Finding level of node of binary tree is equivalent to finding Height of node of binary tree.

Let's understand what is the input and expected output.

Algorithm


There are 2 approach to find level of node in binary tree,
1. Recursive approach.
2. Iterative approach.

Recursive Approach:

In this approach, we will find Level of node in binary tree recursively.

Idea is to do a Preorder traversal of Binary tree.
  1. Initialse variable currentLevel=0 for root, increment to currentLevel +1 while going towards left subtree or right subtree as indication that we are going one level down. 

  2. During preorder traversal, compare given node to see if it matches the current node,

    If No, then we will first search for node on left side and then on right side.

    while moving on any side, increment value of currentLevel.

    If Yes, then return currentLevel.

Note: After each recursive call towards Left subtree or Right subtree, we need to check value received from recursive call, if it is greater than 0, that is the indication that we got the node and level of that node is the returned value from that call. So return the value received as it is.

Java Program to Find Level of node in binary tree Recursive Approach


package tree;

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

/*
          10
        /   \
      5      20
     / \     / \ 
    3   8   15  25 
       /  
      7
 */

public class FindLevelOfNodeInBinaryTree {

 public static void main(String[] args) {

  Node rootNode=null; 
  rootNode  = addNode(rootNode, 10, true);
  rootNode  = addNode(rootNode, 5, true);
  rootNode  = addNode(rootNode, 20, true);
  rootNode  = addNode(rootNode, 3, true);
  rootNode  = addNode(rootNode, 8, true);
  rootNode  = addNode(rootNode, 7, true);
  rootNode  = addNode(rootNode, 15, true);
  rootNode  = addNode(rootNode, 25, true);  

  int nodeData = 15;

  System.out.println(findLevelRecursive(rootNode, nodeData));
 }

 private static int findLevelRecursive(Node startNode, int nodeData){
  return findLevelRecursiveHelper(startNode, nodeData, 0);
 }
 private static int findLevelRecursiveHelper(Node startNode, int nodeData, int level){
  if(startNode==null){
   return -1;
  }
  
  if(startNode.getData() == nodeData){
   return level;
  }
  
  int left = findLevelRecursiveHelper(startNode.getLeft(), nodeData, level+1);
  if(left != -1) return left;
  
  int right = findLevelRecursiveHelper(startNode.getRight(), nodeData, level+1);
  if(right != -1) return right;
  
  return -1;
 }

 private static Node addNode(Node rootNode, int i, boolean isRootNode) {
  if(rootNode==null){
   return new Node(i);
  }else{
   if(i > rootNode.getData()){
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }

   }else{
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }
   }
  }
  return rootNode;
 }

}


Iterative Approach:

In this approach, we will find Level of node in binary tree Iteratively by using Queue.

Idea is to do a traverse the tree level by level, and the current working level at which we found the Node return that level as that is the level/height of that node.
  1. Initialise currentLevel = 0.
    Add the Root node in a Queue and "null" as indication of end of root level.

  2. Do the following until Queue is not empty.
    1. Remove the node from the queue,

    2. If the node is Not Null, it means we are working on node of currentLevel and

      If node value matches with the given value, than that is the node we were looking for, so return currentLevel.


      If node value doesn't match with the given value, than we need to check further nodes,
      Store the Left and Right child (only if it is not null) of current node in Queue for next level processing.

    3. If the node is Null, It means we reached end of currentLevel(because we are adding null only after the end of level.). Increment currentLevel +1 as we are moving one level down.


  Java Program to Find Level of node in binary tree Iterative Approach


package tree;

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

/*
          10
        /   \
      5      20
     / \     / \ 
    3   8   15  25 
       /  
      7
 */

public class FindLevelOfNodeInBinaryTree {

 public static void main(String[] args) {

  Node rootNode=null; 
  rootNode  = addNode(rootNode, 10, true);
  rootNode  = addNode(rootNode, 5, true);
  rootNode  = addNode(rootNode, 20, true);
  rootNode  = addNode(rootNode, 3, true);
  rootNode  = addNode(rootNode, 8, true);
  rootNode  = addNode(rootNode, 7, true);
  rootNode  = addNode(rootNode, 15, true);
  rootNode  = addNode(rootNode, 25, true);  

  int nodeData = 15;

  System.out.println(findLevelIterative(rootNode, nodeData));
 }

 private static int findLevelIterative(Node startNode, int nodeData){
  if(startNode==null){
   return -1;
  }
  
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(startNode);
  queue.add(null);
 
  int currentLevel = 0;
  
  while(queue!=null){
   Node temp = queue.poll();
   
   
   if(temp==null){
    if(queue.peek()!=null){
     queue.add(null);
    }
    currentLevel++;
  
   }else{
    if(temp.getData() == nodeData){
     return currentLevel;
    }
    
    if(temp.getLeft()!=null){
     queue.add(temp.getLeft());
    }
    if(temp.getRight()!=null){
     queue.add(temp.getRight());
    }
   }
  }
  
  return currentLevel;
 }

 private static Node addNode(Node rootNode, int i, boolean isRootNode) {
  if(rootNode==null){
   return new Node(i);
  }else{
   if(i > rootNode.getData()){
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }

   }else{
    if(isRootNode){
     Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
     rootNode.setLeft(nodeToAdd);
    }else{
     Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
     rootNode.setRight(nodeToAdd);
    }
   }
  }
  return rootNode;
 }

}

You may also like to see


Compress a given string in-place and with constant extra space.

Check whether a given string is an interleaving of String 1 and String 2.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Serialize and Deserialize a Binary Tree

Advanced Multithreading Interview Questions In Java



Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment