Challenge: Find the Height of a Binary Search Tree

Given the root to a Binary Search Tree, write a function to find the height of the tree. A solution is placed in the "solution" section to help you, but we would suggest you try to solve it on your own first.

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 NodeMaximum 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:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.