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.
- 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.
- 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 javabypatel.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.
- Initialise currentLevel = 0.
Add the Root node in a Queue and "null" as indication of end of root level. - Do the following until Queue is not empty.
- Remove the node from the queue,
- 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. - 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 javabypatel.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
Top Binary tree interview questions in Java
Find Kth SMALLEST element in BST(Binary Search Tree)
Check whether Binary Tree is foldable or not.
Check if two nodes are cousins in a Binary Tree.
Get Level/Height of node in binary tree
Print nodes at K distance from Leaf node in Binary tree.
Construct a Binary Tree from In-order and Post-order traversals.
Print Nodes in Top View of Binary Tree.
Zig Zag Traversal of Binary Tree.
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.
Advanced Multithreading Interview Questions In Java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment