Binary search trees

Steps

1. Remind the class how binary search works on a sorted list.
2. Show the tree: lines to follow and nodes with hidden numbers underneath.
3. Pick a target. The child starts at the top node and turns it over.
4. If the target is smaller, go left. If it is bigger, go right. Repeat until you find it.
5. Let children arrange new numbers into their own tree shapes.
6. Compare how many nodes you visit with searching a list.

Talk about it

• Does the shape of the tree change the search?
• How is this different from binary search on a list?
• Where could a computer use a tree?