Name Date Period

← CS Unplugged

CS Unplugged activity

Binary Search Trees: Find the Number

About 20 minutesSoloPencil

A binary search tree stores numbers so you can find any one of them fast, without checking every number first. Each circle points down to two smaller circles, and one simple rule tells you which way to go.

The vocabulary

The top circle is the root. Every circle is a node, joined by branches. A node with no branches below it is a leaf.

How it works

Just an example, not one of your questions. Target: 6.

Your turn

1. Start at the root.
2. Compare your target to the number in the circle.
3. Go left if your target is smaller, right if it is larger.
4. Write down every number you check, in order.
5. If you run out of tree before you find your target, it isn’t in there.

One more check. For any target above, how many checks would the sorted list take, scanned left to right? Write that count in the linear-list column too.

Learn more: binary search trees on Wikipedia.

Check your answers