SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/tech-balanced-tree-height

Why do binary search trees try to stay balanced?

To keep the height about log n, so searches stay O(log n) instead of O(n).

Start playing free

  1. To use less memory per node
  2. So every key appears twice
  3. To keep the tree's height about log n ✔

Why: Finding a key in a binary search tree walks from the root down one path, so the time depends on the tree's height. A lopsided tree can be as tall as a list, but a balanced one stays about log n tall.

Huh, didn't know that: Insert sorted numbers into a plain binary search tree and it turns into a straight line, the worst case.

The dad joke
Why did the binary tree go to yoga? To work on its balance.
Like this card?
Play the game

References

Answer: To keep the tree's height about log n. Finding a key in a binary search tree walks from the root down one path, so the time depends on the tree's height. A lopsided tree can be as tall as a list, but a balanced one stays about log n tall.

  1. MIT 6.006 Introduction to Algorithms, Lecture 6: Binary Trees I ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec6
    Keep a binary tree balanced after insertion or deletion. Reduce O(h) running times to O(log n) by keeping h = O(log n)
    Checked 2026-10-10.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Tech & GadgetsHow fast is binary search on a sorted array of n items, in Big O terms?Tech & GadgetsIn Big O notation, what do you ignore when describing an algorithm's running time?Tech & GadgetsWhat is the worst-case running time of insertion sort on n items?

That's stuff everyone should know.