What is a binary search tree?
A binary search tree is a set of nodes where each node has at most two children. Smaller values sit on the left and bigger values on the right. That order lets you find a value by throwing away half of what is left at every step.
A phone's contact list and a database index use ideas like this to search millions of entries quickly.
By the end of this lesson
Note
I can build and search a binary search tree.
Key words
| Word | What it means |
|---|---|
| Tree | nodes joined from one top node downwards |
| Root | the top node of a tree |
| Leaf | a node with no children |
| Child | a node directly below another node |
| In-order walk | visit left, then the node, then right |
| Recursion | a function that calls itself on a smaller problem |
The cells students fill in are left blank in this preview.
Smaller goes left, bigger goes right
Each node of a tree holds a value and up to two links, left and right. The top node is the root.
The rule of a binary search tree is simple. Everything in a node's left side is smaller than the node. Everything in its right side is bigger.
Worked example: inserting 6 into the tree
| Step | Compare | Decision |
|---|---|---|
| 1 | 6 with the root 8 | 6 is smaller, go left |
| 2 | 6 with 3 | 6 is bigger, go right |
| 3 | The right of 3 is empty | Put 6 there |
The cells students fill in are left blank in this preview.
A function that calls itself walks a tree
A tree is a node whose left and right sides are smaller trees. So one function can handle a tree by handling its two smaller trees.
This is recursion. It needs a base case that stops it: an empty tree, None, answers at once. Without the base case, the function would call itself for ever.
Build the tree and walk it
# A binary search tree: smaller values go left, bigger go right.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for number in [8, 3, 10, 1, 6]:
root = insert(root, number)
print(in_order(root))
# Insert 7 as well, then print again.
An in-order walk gives the values in order
To walk in order, do three things. Walk the whole left side. Visit the node. Walk the whole right side.
Because the left is smaller and the right is bigger, the values come out sorted. The shell's sort -n gives the same order for the same numbers.
The same numbers in sorted order
printf '8\n3\n10\n1\n6\n' | sort -nShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: walking the tree in order
| Step | Where the walk is | Value written |
|---|---|---|
| 1 | Left of 8, then left of 3 | 1 |
| 2 | Back at 3 | 3 |
| 3 | Right of 3 | 6 |
| 4 | Back at 8 | 8 |
| 5 | Right of 8 | 10 |
The cells students fill in are left blank in this preview.
Tree shape decides how fast it is
A search follows one path from the root, so its cost is the height of the tree. A balanced tree of 1,000 values is about 10 levels tall.
If you insert 1, 2, 3, 4 in that order, each value goes to the right of the last. The tree becomes a line, and a search checks every node.
A common mistake
Warning
Many people think a binary search tree is always fast. It is fast only when it is balanced. Inserting values that are already sorted builds a line, as slow as a linked list. The order the values arrive in decides the shape.