# Height of Binary Search Tree - Recursive Approach

In this article, we are going to see how to get the height of a Binary Search Tree using a Recursive 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

In this problem we can divide the problem into smaller parts by using:

Height of Tree = 1 + MAX(Height of Left Subtree, Height of Right Subtree)

And then we further apply the same to the left subtree and to the right subtree till we reach the Base Case of the subtree being null and then we return -1.

Below is an example of a Binary Tree:

The height of the Below Binary Tree is 2

So the height of Node 4 = 1 + MAX(Height of Node 2 + Height of Node 7) = 1 + MAX(1,0) = 2

#### Algorithm

- If the node is null, it means that the tree is empty and so return -1
- Get the leftHeight by calling the function and passing the left of the node to it
- Get the rightHeight by calling the function and passing the right of the node to it
- Get the max of leftHeight and rightHeight and store it in maxHeight
- Return maxHeight + 1

#### Complexity

- Time Complexity: O(N)
- Auxiliary Space Complexity: O(Height of Tree)

The Time Complexity will be O(N) as visit every node once, and the space complexity will be O(Height of Tree) which is O(logN) for a perfect binary tree, the Space Complexity is because of the stack memory consumed by the recursive calls.

#### Code

```
# Java Code
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 getHeightRecursive() {
// call the callback function and provide the root
return getHeightCallback(root);
}
private int getHeightCallback(Node node) {
// If the node is null then it's height is given as -1
if (node == null)
return -1;
// Get the height of both left and right node
int leftHeight = getHeightCallback(node.left);
int rightHeight = getHeightCallback(node.right);
// Store the max of left and right node height in maxHeight
int maxHeight = Math.max(leftHeight, rightHeight);
// since the node will have 1 + maxHeight of children
// As the node is 1 height above the childrens
return maxHeight + 1;
}
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.getHeightRecursive();
System.out.println("Height of Binary Tree: " + height);
}
}
```

##### Output

`Height of Binary Tree: 2`