Binary Search Tree

Build a binary search tree by hand and see how its shape decides what lookup costs.

7 nodesheight 3✓ balancedmin 20 · max 80
20304050607080

In-order

20 → 30 → 40 → 50 → 60 → 70 → 80

Left, node, right. On a BST this always comes out sorted — which is the whole point of the shape.

Why height matters

Lookup costs one comparison per level, so a balanced tree of 7 nodes finds anything in about 3 steps. This one is 3 deep.

search(node, v)

Run an operation above to step through it

  1. while node is not empty:
  2. if v = node.value: return found
  3. if v < node.value: node ← node.left
  4. else: node ← node.right
  5. return not found ▸ one step per level
About

Every node holds a value larger than everything in its left subtree and smaller than everything in its right, which is exactly what makes an in-order walk come out sorted.