Solution: Find the Height of Binary Search Tree

Let’s solve the Find the Height of a Binary Search Tree problem.

We'll cover the following

Statement

Given the root of a binary search tree, return the height of the tree. The height of the tree is the length of the longest path from the root node to any leaf node in the tree.

Note: The height of an empty tree is 0, whereas the height of a tree with a single node is 1.

Constraints:

  • −104≤-10^{4} \leqNode.data ≤104\leq 10^{4}

  • The tree contains nodes in the range [1,500][1, 500].

Solution

To find the height of a given binary search tree, we utilize the depth-first searchDFS (DFS) method, starting from the root node of the tree. By traversing the tree recursively, we explore each node’s left and right subtrees to reach the farthest leaf node. Leveraging the preorder traversal method, we first visit the root node, followed by its left child and then its right child. At each node, we record its height. Finally, we return the maximum height among the left and right subtrees, incremented by one to account for the root node’s height.

We will follow this algorithm to reach the solution:

  1. Start from the root node and check whether it exists. If the root node does not exist, return 0.

  2. Otherwise, recursively perform the following steps:

    1. Visit the left child of the current node and calculate its height by recursively calling the function to find the height of the left subtree.

    2. Explore and calculate the height of the right child by recursively calling the function to find the height of the right subtree.

    3. Take the maximum of both heights obtained in the above steps, then add 11 to account for the current node.

  3. At the end, return this calculated height of the tree.

Let’s have a look at the following illustrations for a better understanding of the algorithm above:

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