Trees: the binary search tree

What you will be able to do

After this lesson you can

• explain what a tree, a root, a child and a leaf are,
• insert into and search a binary search tree,
• walk it in order to get sorted values, and
• explain why the shape of the tree matters.

A family tree for data

A tree is a structure of nodes where each node can have children. The first node, at the top, is the root. A node with no children is a leaf. Think of a family tree, or of the folders on a computer: a folder holds folders, which hold more folders. A tree needs no loops back, so every node has exactly one parent, except the root.

In a binary tree, each node has at most two children: a left one and a right one. A binary search tree (BST) adds a rule that makes searching fast:

For every node, everything in its left part is smaller, and everything in its right part is bigger.

Look at the picture. The root is 8. On its left are 3, 1 and 6: all smaller than 8. On its right are 10 and 14: all bigger. And the rule holds at every node: under 3, the 1 is to the left, and the 6 to the right.

Predict first. What does in_order() give, although the values were inserted as 8, 3, 10, 1, 6, 14, 6? Then run it.

Insert and search

• Insert follows the rule: start at the root. If the new value is smaller, go left. If bigger, go right. When you reach an empty place (None), put the new node there. A value that is already there is ignored, so the tree holds each value once. The last 6 in the list changes nothing.
• Search follows the same path. Compare with the node: equal means found; smaller, go left; bigger, go right. If you reach None, the value is not there. The program counts the steps: contains(6) takes 3 steps (8, then 3, then 6) and contains(7) takes 4 steps and fails (8, 3, 6, and then the right of 6 is empty).

Each step throws away a whole side. This is the same idea as binary search in a sorted list. For a balanced tree of a million values, a search needs about 20 steps.

The in-order walk

The method in_order visits the nodes in a special order, with recursion:

1. walk the left part (all the smaller values),
2. visit the node itself,
3. walk the right part (all the bigger values).

The result is [1, 3, 6, 8, 10, 14]: the values in sorted order. The tree sorted them for free. That is a very useful property: a BST keeps its values in order while you add and remove them, and you can read them in order at any time. (Compare with a sorted list, where each insertion has to move many items.)

The function walk is written inside in_order, so that it can use result. Three lines are all it takes: recursion matches the structure of a tree beautifully, because a tree is made of smaller trees.

The in-order walk of the code below always gives the values sorted, however they arrived.

Height, and the shape of the tree

The height is the number of levels, from the root down to the deepest leaf. The tree above has height 3. The height decides the cost of a search: you take at most height steps.

But the shape depends on the order of insertion.

So a BST is fast on average, when the values arrive in a mixed order, and can be slow when they arrive sorted. Real systems use self-balancing trees, which rearrange themselves, to keep the height small. That is a topic for a later course. For now, remember that the shape matters.

Common mistakes

• Forgetting the None check in the recursion, so that the walk fails on an empty part.
• Breaking the rule: putting a value in the wrong side.
• Forgetting that duplicates are ignored, or decide what they should do (go left, or count them).
• Expecting a search to be fast on a tree that is a chain.
• Writing value < node.value and value > node.value and forgetting the equal case.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the lab Binary search tree. You finish a BST class, and the checker tries it.
2. Build. Open the problem Build the tree on paper and the problem Height of a tree.
3. Stretch. Open the problem Smallest and biggest and find them without the walk.

Remember these

• A tree has a root, and nodes with children. A binary tree has a left and a right child at most.
• A BST: left is smaller, right is bigger, at every node.
• Insert and search follow one path down: smaller go left, bigger go right.
• The in-order walk (left, node, right) gives the values sorted.
• The shape matters: sorted input gives a chain with height n.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Where does the value 7 go in the tree of the lesson?

2. What does the in-order walk give for a BST?

3. What is the height of a tree that is a chain of 5 nodes?