Binary Search Tree
BST
Tree Height
Data Structures
Algorithms

Finding height in Binary Search Tree

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Introduction

Finding the height of a binary search tree is a standard recursion problem, but the definition matters. Some textbooks define height as the number of edges on the longest path from the root to a leaf, while others count nodes instead. Pick one convention and stay consistent.

What Height Means

In this article, height means the number of edges on the longest downward path.

  • an empty tree has height -1
  • a single-node tree has height 0
  • every other tree has height 1 + max(left_height, right_height)

The fact that the tree is a binary search tree does not actually change the height algorithm. Height depends on shape, not on ordering. A plain binary tree and a BST use the same approach here.

Recursive Solution

Recursion is the clearest solution because the height of a node depends on the heights of its children. The Python example below builds a small BST and computes its height.

python
1from dataclasses import dataclass
2from typing import Optional
3
4@dataclass
5class Node:
6    value: int
7    left: Optional["Node"] = None
8    right: Optional["Node"] = None
9
10
11def height(root: Optional[Node]) -> int:
12    if root is None:
13        return -1
14
15    return 1 + max(height(root.left), height(root.right))
16
17
18root = Node(
19    8,
20    left=Node(3, left=Node(1), right=Node(6, left=Node(4), right=Node(7))),
21    right=Node(10, right=Node(14, left=Node(13))),
22)
23
24print(height(root))

The function works from the bottom up. Every leaf returns 0 because both missing children return -1. Their parent then becomes 1 + max(-1, -1), which is 0. That pattern repeats until the root gets the height of the full tree.

This solution visits each node once, so the time complexity is O(n), where n is the number of nodes. The call stack uses O(h) space, where h is the tree height.

Iterative Level-Order Solution

If you want to avoid recursion, breadth-first traversal also works. The idea is to process the tree one level at a time and count how many levels exist.

python
1from collections import deque
2
3
4def height_iterative(root: Optional[Node]) -> int:
5    if root is None:
6        return -1
7
8    queue = deque([root])
9    levels = -1
10
11    while queue:
12        for _ in range(len(queue)):
13            node = queue.popleft()
14            if node.left is not None:
15                queue.append(node.left)
16            if node.right is not None:
17                queue.append(node.right)
18        levels += 1
19
20    return levels
21
22
23print(height_iterative(root))

This version is also O(n) in time. It can be preferable when the tree is very deep and you want to avoid recursion depth issues in languages with a small recursion limit.

Why Height Matters

Height is a proxy for performance in tree-based structures. Search, insert, and delete in a BST take time proportional to the height of the tree. A balanced tree keeps height near O(log n), while a badly skewed tree can degrade to height O(n).

That is why self-balancing trees such as AVL trees and red-black trees exist. They are designed to prevent the shape from becoming too tall after repeated insertions and deletions.

Common Pitfalls

  • Mixing the edge-based and node-based definitions of height. Most off-by-one errors come from that mismatch.
  • Returning 0 for an empty tree when the rest of the algorithm assumes edge count. That changes every result by one.
  • Thinking the BST ordering rule changes the height algorithm. It does not; only the tree shape matters.
  • Forgetting that a highly skewed BST can cause deep recursion.
  • Recomputing subtree heights repeatedly inside another loop, which can turn a linear traversal into something slower.

Summary

  • Height is usually computed as the longest path from root to leaf under a chosen counting convention.
  • A simple recursive definition gives a clean O(n) solution.
  • A breadth-first traversal provides an iterative alternative with the same time complexity.
  • The BST property does not change how height is calculated.
  • Height matters because tree operation costs depend on it.

Course illustration
Course illustration

All Rights Reserved.