Course contentsShow
← Computer Science
Lesson 521 of 2,87212. Binary Search TreesFree lesson

BST Height and Balance

Understanding how tree height affects performance and the difference between balanced and unbalanced BSTs.

BST Height and Balance

You'll learn why the height of a Binary Search Tree matters and what makes one "balanced" or "unbalanced."

Why Height Matters

A BST's height is the length of the longest path from root to leaf. This single number dramatically affects performance. Remember that BST operations like search, insertion, and deletion navigate from root downward—so height determines how many steps you'll take.

In a balanced BST, operations take O(log n) time because the tree grows "wide" rather than "tall." With n nodes, a balanced BST has height approximately log₂(n). For 1,000 nodes, that's only about 10 levels to traverse.

The Problem: Unbalanced Trees

An unbalanced BST leans heavily to one side. In the worst case—inserting already-sorted data like [1, 2, 3, 4, 5]—you get a tree that looks like a linked list! Each node has only a right child, creating height = n.

Balanced (height 2):        Unbalanced (height 4):
      4                           1
     / \                           \
    2   6                           2
   / \                               \
  1   3                               3
                                       \
                                        4
                                         \
                                          5

In the unbalanced version, searching for 5 requires 5 comparisons instead of 3. Operations degrade from O(log n) to O(n)—as slow as a linked list!

What Makes a Tree Balanced?

A balanced tree keeps left and right subtree heights roughly equal at every node. The exact definition varies (AVL trees, Red-Black trees use different criteria), but the goal is consistent: maintain height ≈ log(n).

Key Takeaway: BST height determines operation speed—balanced trees maintain O(log n) performance with height ≈ log(n), while unbalanced trees can degrade to O(n) when height approaches n.