Binary Tree: Find the height - Iterative approach
Write a program to find the height of a binary tree using iterative approach
The height of the Binary Tree is defined as the number of edges in the longest path from the root to the leaf node
Edge Cases for height of the Binary Tree
- If root is null, no nodes are present in the Binary Search Tree then Height is -1
- If only one node is present i.e root then the Height is 0
Note
There are various interpretations for height of a binary tree.
Some people consider height in terms of edges (the line connecting the two nodes) while other people consider the no of nodes in the longest path from root to leaf node.
And some people also consider levels to calculate height (root node is at level 1, its child nodes are at level 2 and the final leaf nodes are at level n, so the height becomes n)
So its important to call out how do you interpret the height of a binary tree
Here we are considering levels of the binary tree to calculate the BT height
Approach
To find the height of a Binary Tree using Iterative Approach we traverse the given Binary Search Tree Level by Level and keep incrementing the height variable.
We will use Breadth First Search Traversal for level wise traversal on the Binary Tree
Algorithm
- Create a variable height having value -1
- If the root of the tree is null, then return -1
- Create a currentLevelNodes Queue and insert root of BT in it, this Queue is used for the BFS traversal
- While the currentLevelNodes is not empty do
- Create a nextLevelNodes Queue to store all the nodes in the next level
- While currentLevelNodes is not empty do
- Get the First Node from the currentLevelNodes and store it in a variable named current
- If left of current is not null, then push left of current to nextLevelNodes
- If right of current is not null, then push right of current to nextLevelNode
- Copy the nextLevelNodes to the currentLevelNodes
- Increment the value of Height by 1
- Return Height
Diagram
Complexity
Time Complexity : O(n) , where n is the number of nodes in binary tree
Space Complexity: O(Max Width of the BT)
The Time Complexity will be O(N) as visit every node once.
The space complexity will be O(Max Width of the BT) is because of the Queue used to store the nodes in the current and next level of the Binary Tree
Java Code
import java.util.ArrayDeque;
import java.util.Queue;
class BinaryTreeHeightIterative{
// Node Class to represent the each node of BinaryTree
static class Node {
int data;
Node left, right;
// Constructor to set the value of the node
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
private Node root = null;
// A function which prints the level order traversal representation of the Binary Tree
static void printTree(Node root) {
// Queue to store the current level of the binary tree
Queue currentLevelQueue = new ArrayDeque();
currentLevelQueue.offer(root); // Insert the root to the queue
while (!currentLevelQueue.isEmpty()) {
// Create a temporary queue to store the nodes of next level
Queue tempQueue = new ArrayDeque();
while (!currentLevelQueue.isEmpty()) {
// Get the node from the queue and print it
Node current = currentLevelQueue.poll();
System.out.print(current.data);
// If current node has left then insert it to the tempQueue
if (current.left != null) {
tempQueue.offer(current.left);
}
// If current node has right then insert it to the tempQueue
if (current.right != null) {
tempQueue.offer(current.right);
}
}
// Printing a new line at each level end
System.out.println();
// copy the contents of the tempQueue to the currentLevelQueue
currentLevelQueue = tempQueue;
}
}
public int getHeightIterative(Node node) {
// Create a variable to store the height
int height = -1;
// If the root is null then the height of the tree is -1
if (node == null) {
return -1;
}
Node temp = node;
// Create a queue to store the nodes in the current level of the bfs traversal
Queue currentLevelNodes = new ArrayDeque();
// Push the root to the queue to initialize it
currentLevelNodes.offer(temp);
// Run the loop till we have node in the current level
while (!currentLevelNodes.isEmpty()) {
// Create a queue to track the next level nodes
Queue nextLevelNodes = new ArrayDeque();
// Loop through all the nodes in the current level
while (!currentLevelNodes.isEmpty()) {
// Get the current node from the queue
Node current = currentLevelNodes.poll();
// Check if the current has children and push the children in nextLevelQueue
if (current.left != null) {
nextLevelNodes.offer(current.left);
}
if (current.right != null) {
nextLevelNodes.offer(current.right);
}
}
// Copy the next level nodes into the current level queue
currentLevelNodes = nextLevelNodes;
// Increment the height as we go to the nextLevel
height++;
}
return height;
}
public static void main(String[] args) {
// Creating a simple binary tree using the node class
Node tree1 = new Node(1);
tree1.left = new Node(2);
tree1.right = new Node(3);
tree1.left.left = new Node(4);
tree1.left.right = new Node(5);
tree1.right.left = new Node(6);
tree1.right.right = new Node(7);
BinaryTreeHeightIterative btHeight = new BinaryTreeHeightIterative();
printTree(tree1);
int height = btHeight.getHeightIterative(tree1);
System.out.println("Height of Binary Tree: " + height);
}
}
Output
1
23
4567
Height of Binary Tree: 2