data structures~16 minRoute 02 7 of 9

Trees & BSTs

Branching structures — and the search tree that makes lookup logarithmic.

Story — a librarian who sorts as she shelves

A linked list is a single line — to find anything, you walk it. A tree is a line that branches: each node has two children. That branching is the trick.

A binary search tree (BST) adds one rule: every value in a node's left subtree is smaller than the node; every value in the right subtree is larger. With that invariant, a search at the root either finds the value or splits the remaining work in half. Sound familiar? It's binary search, but the data structure keeps itself sorted as you insert.

Branchy says

A balanced BST gives O(log n) lookup, insert, and delete — the three common operations all stay fast. Compare with a sorted array: O(log n) lookup, but O(n) insert (shift everything).

See it — insert and search the BST

Insert a value and watch where it lands — left if smaller, right if larger. Search highlights the path from root to target. Notice how the path length grows much slower than the tree size.

Seven values inserted into a BST.

InsertSearch

Branchy says

In a BST, every left subtree is smaller, every right subtree is larger. That invariant is what makes lookup log time — when balanced.

Try it — build a worst-case tree

Exercise. Reset the tree, then insert 1, 2, 3, 4, 5, 6 in that order. Look at the shape. What just happened?

Reveal answer

Each new value is bigger than every previous one, so it always goes right. The "tree" is a chain — effectively a linked list. Search degenerates from O(log n) to O(n). This is exactly what self-balancing BSTs (red-black trees, AVL trees) prevent.

Code it — five languages, one invariant

The code shape is identical across languages: a recursive insert and a recursive search. Each one says "if smaller, go left; if larger, go right; if equal, found."

class Node:
    def __init__(self, v): self.v, self.left, self.right = v, None, None

def insert(node, v):
    if node is None: return Node(v)
    if v < node.v: node.left  = insert(node.left, v)
    if v > node.v: node.right = insert(node.right, v)
    return node

def search(node, v):
    if node is None: return False
    if v == node.v:  return True
    return search(node.left if v < node.v else node.right, v)

Quiz it — make it stick

Question 1
What's the BST invariant?
Each node's left child is smaller, right child is larger, and all descendants follow the same ruleEach node has at most two childrenAll leaves are at the same depthThe tree is sorted in level order
True or false — Question 2
A BST always gives O(log n) lookup.
Predict — Question 3
Insert 5, 3, 7, 1 (in order) into an empty BST. Then search for 7. How many nodes are visited?
```
# Tree shape after inserts:
#       5
#      / \
#     3   7
#    /
#   1
```
Your guess

No Dumb Questions

Real questions other learners asked on this page.

Why bother with a BST when I can just sort an array?
A BST keeps itself sorted as you insert and delete — O(log n) per operation. Re-sorting an array on every insert is O(n log n) per insert, which is much worse if your data changes often.
What goes wrong if my BST becomes unbalanced?
In the worst case it degenerates into a linked list — every operation becomes O(n). Self-balancing BSTs (red-black trees, AVL trees) automatically rebalance to keep the height O(log n). Modern map/dict implementations often use these under the hood.
What's the difference between a tree and a graph?
A tree is a connected, acyclic graph with one designated root. A graph is more general — can have cycles, multiple components, no root. Every tree is a graph; not every graph is a tree.