TwiddleLab / Code / Data Structures You Can See

Binary Search Trees

Lesson 7 of 10 · 7 min · Free, no account needed

What you will learn

• A binary search tree keeps one rule at every node: smaller values in the left branch, bigger in the right.
• Inserting and searching both walk one path from the root down, one check per level.
• The height (number of levels) decides the speed. A bushy tree of n nodes has about log2 n levels.
• Insert sorted data and the tree becomes a stick: n levels, as slow as a list.

Start the lesson

How the lesson goes

1. A contact list where adding is fast and finding is fast. Can you have both?

   This tree of numbers was built with one rule. Where would 7 go?

2. Build the tree yourself.

   Each number starts at the top. At every node: smaller goes left, bigger goes right.

   Each comparison sends the number into one branch and ignores the other. So a new number always ends up at an empty spot where the rule still holds.

3. Now search it.

   Is 13 in the tree? Is 5? Step through and count the checks.

4. A binary search tree.

   A binary search tree (BST): every node has at most two children, and at every node, smaller values go left and bigger ones go right.

   Insert and search walk one path down from the root: at most one check per level.

   The number of levels is the tree's height. Height decides how fast it is.

5. Your contacts arrive already sorted: 1, 2, 3, 4, 5, 6, 7.

   What shape will the tree have? Tap your bet and watch.

6. Bushy tree.

   Same 7 numbers, different order. Swap them until the tree is only 3 levels tall.

7. A perfectly bushy tree holds 1 000 000 contacts. About how many levels does it have?

   Each level holds twice as many nodes as the one above it: 1, 2, 4, 8, ...

   A full tree with h levels holds 2^h - 1 nodes. 2^19 - 1 = 524 287 is too few and 2^20 - 1 = 1 048 575 is enough, so 20 levels. In math that's log2 1 000 000, about 19.9, rounded up.

8. Be the search.

   Tap the nodes a search for 45 checks, in order.

9. Race: the stick against your bushy tree.

   Which one finds contact 7 in fewer checks? Tap it, then Check.

   Search walks one path from the root, one node per level. Your tree has 3 levels, the stick has 7. With a million contacts that's about 20 checks against up to a million.

Previous lesson: Trees: Folders Inside Folders · Next lesson: Heaps and Priority Queues · Part of the course: Data Structures You Can See

Lessons are interactive and need JavaScript. Turn it on to play them.