Binary Search Trees
Smaller left, bigger right.
A binary search tree follows one rule. Everything in a node's left subtree is smaller than it, and everything in its right subtree is bigger. That rule turns a tree into something you can search like binary search.

- One rule
- Smaller on the left
- Bigger on the right
Searching a BST
Our sample tree is a binary search tree. To find a value, start at the root. If the target is smaller, go left. If it's bigger, go right. Each step throws away a whole subtree. We print the path. Run it. Finding thirteen takes just four steps.
from tree import sample
def search(node, target):
path = []
while node:
path.append(node.value)
if target == node.value:
return path
node = node.left if target < node.value else node.right
return path + ["not found"]
print(search(sample(), 13))
print(search(sample(), 5))[8, 10, 14, 13] [8, 3, 6, 4, 'not found']
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'BST costs
In a balanced binary search tree, searching, inserting, and deleting are all O of log N, because each step halves what's left. And an in order traversal lists every value in sorted order. That's why databases and sorted maps are built on trees like this.
| key | value |
|---|---|
| Search | O(log n) when balanced |
| Insert | O(log n) when balanced |
| In order | sorted output |
| Used in | databases, sorted maps |
Summary
In a binary search tree, smaller values go left, and bigger values go right. Searching follows one path down. Next, building one by inserting values.
Key takeaways- Left < node < right
- Follow one path
- O(log n) when balanced