# Find Height of node in Binary tree in Java

### Get Height of Node in Binary Tree.

Given a binary tree, Find the height of a given node in Binary tree.

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

### Algorithm

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

Recursive Approach:

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

Idea is to do a Preorder traversal of Binary tree.
1. Initialse variable currentHeight=0 for root, increment to currentHeight +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
currentHeight.

If Yes, then return
currentHeight.

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 height of that node is the returned value from that call. So return the value received as it is.

### Java Program to Find Height of node in binary tree Recursive Approach

```package tree;

import java.util.Queue;

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

public class FindLevelOfNodeInBinaryTree {

public static void main(String[] args) {

Node rootNode=null;

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){
}else{
}

}else{
if(isRootNode){
}else{
}
}
}
return rootNode;
}

}

```

Iterative Approach:

In this approach, we will find Height 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 height of that node.
1. Initialise currentHeight = 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 currentHeight and

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

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 currentHeight(because we are adding null only after the end of level.). Increment currentHeight +1 as we are moving one level down.

### Java Program to Find Height of node in binary tree Iterative Approach

```package tree;

import java.util.Queue;

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

public class FindLevelOfNodeInBinaryTree {

public static void main(String[] args) {

Node rootNode=null;

int nodeData = 15;

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

private static int findLevelIterative(Node startNode, int nodeData){
if(startNode==null){
return -1;
}

int currentLevel = 0;

while(queue!=null){
Node temp = queue.poll();

if(temp==null){
if(queue.peek()!=null){
}
currentLevel++;

}else{
if(temp.getData() == nodeData){
return currentLevel;
}

if(temp.getLeft()!=null){
}
if(temp.getRight()!=null){
}
}
}

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){
}else{
}

}else{
if(isRootNode){
}else{
}
}
}
return rootNode;
}

}
```