Challenge: Find the Height of a Binary Search Tree

Problem Statement

In this problem, you have to implement the findHeight() function to find the height of a given Binary Search Tree. The method for finding the height of a simple Binary Tree can be used. An illustration is also provided for your understanding.

• Height of a Node — Maximum number of connections between the node and a leaf node in its path.
• Height of a Tree — Height of its root node

Also, keep in mind that the height of an empty tree and leaf nodes is zero.

Function Prototype

int findHeight(Node root);

Here, root is the root node of the Binary Tree.

Output

It returns the maximum depth or height of the Binary Tree.

Sample Input

bst = {
		6 -> 4,9
    4 -> 2,5
    9 -> 8,12
    12 -> 10,14
}
where parent -> leftChild,rightChild

Sample Output

3

Explanation

Starting from the farthest leaf node (10) and moving back to the root (6) will give the height. The height of Node 10 is 0, the height of Node 12 is 1, the height of Node 9 is 2, and the height of the tree or the height of the root node is 3. Here’s an illustration of the given challenge: