Height of Binary Search Tree - Iterative Approach
In this article, we will see how to get the height of a Binary Search 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.
Base Case Height of the Binary Search Tree:
- If the root is null, no nodes are present in the Binary Search Tree then the Height is -1
- If only one node is present i.e root then the Height is 0
To find the height of a Binary Search Tree using iterative approach we traverse the given Binary Search Tree level by level and keep incrementing the height variable. So to travel level by level we use Breadth First Search Traversal on the Binary Search Tree.
Below is an example of a Binary Search Tree:
Traversal of the Binary Search Tree level by level will be
Height 0: 4
Height 1: 2 7
Height 2: 1 3
The height of the Below Binary Tree is 2
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 BST 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
Complexity
- Time Complexity: O(N)
- Space Complexity: O(Max Width of the BST)
The Time Complexity will be O(N) as visit every node once, and the space complexity will be O(Max Width of the BST), the Space Complexity is because of the Queue used to store the nodes in the current and next level of the Binary Search Tree.
Code
# Java Code
import java.util.ArrayDeque;
import java.util.Queue;
class BinarySearchTree {
class Node {
// Node class for Binary Search Tree
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;
// Insert array of num into the BST
public void insertArray(int nums[]) {
for (int i = 0; i < nums.length; i++) {
insert(nums[i]);
}
}
// Insert a value in BST Iteratively
public void insert(int data) {
// Check if root is null,
// if null then create a node and make it root
if (root == null) {
root = new Node(data);
return;
}
// Start traversing from the root and find the position of node to insert
Node current = root;
while (current != null) {
if (data < current.data) {
// Insert the node if the position is empty
if (current.left == null) {
current.left = new Node(data);
return;
}
current = current.left;
} else {
if (current.right == null) {
// Insert the node if the position is empty
current.right = new Node(data);
return;
}
current = current.right;
}
}
}
public int getHeightIterative() {
// Create a variable to store the height
int height = -1;
// If the root is null then the height of the tree is -1
if (root == null) {
return -1;
}
// Create a queue to store the nodes in the current level of the bfs traversal
Queue<Node> currentLevelNodes = new ArrayDeque<Node>();
// Push the root to the queue to initialize it
currentLevelNodes.offer(root);
// Run the loop till we have node in the current level
while (!currentLevelNodes.isEmpty()) {
// Create a queue to track the next level nodes
Queue<Node> nextLevelNodes = new ArrayDeque<Node>();
// 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) {
int[] nums = { 4, 7, 2, 1, 3 };
BinarySearchTree bst = new BinarySearchTree();
bst.insertArray(nums);
// It gives height of the binary tree height of the root node is 0,
// and if no node is there we take -1
int height = bst.getHeightIterative();
System.out.println("Height of Binary Tree: " + height);
}
}
Output
Height of Binary Tree: 2