Trees and Graphs

Trees and binary search trees

Branching structure and ordered lookup

~12 minLesson 10 of 25Written by Claude Opus 4.8

Arrays are flat; the world is nested. Trees model hierarchy - and one small ordering rule turns a tree into a searchable index that finds any value in a handful of steps... as long as it stays balanced.

A tree is what you get when data branches: a file system, a family tree, the DOM, a decision. A binary search tree (BST) adds one promise - everything smaller sits left, everything larger sits right - and that single invariant lets you find, insert, or delete a value in $O (lo g n)$ steps when the tree is balanced. Break the balance and it quietly decays back into a linked list at $O (n)$ . This lesson makes you feel exactly where that line is.

The vocabulary in one breath

The top node is the root. Each node points to children; the node above is its parent. A node with no children is a leaf. A node's depth is how many edges lie between it and the root (root has depth 0). The tree's height is the depth of its deepest leaf - the length of the longest root-to-leaf path. In a binary tree, every node has at most two children: a left and a right.

The ordering rule that makes search cheap

A plain binary tree is just structure. A binary search tree imposes a rule at every node, not just the root:

The BST invariant

For every node with value $v$ , all values in its left subtree are $< v$ and all values in its right subtree are $> v$ .

Because this holds recursively, searching is just repeated binary decisions. From the root you compare once, then walk left or right - throwing away an entire subtree with each step, exactly like binary search on a sorted array. Each comparison drops you one level, so the work is proportional to the height $h$ :

search / insert / delete = O (h) .

When the tree is balanced, $h \approx ⌊ lo g_{2} n ⌋$ , so every operation is $O (lo g n)$ . That is the whole reason BSTs exist.

The BST sandbox

Type a value and hit Insert (or click a value chip, or Random) and watch it fall into place: at each node it compares, then commits left or right, until it lands in an empty slot as a new leaf. Then press In-order traversal - the visit order comes out sorted. Finally, hit the degenerate preset and watch a tree collapse into a straight line while the height readout climbs.

BST sandbox

insert · traverse · balanced vs. skewed

value

click to add:

comparing nowpath takennew leaf / visitedcurrent visit

Insert values and watch each one follow left < node < right down to its slot.

in-order output:

nodes 7height 2balanced ✓ O(log n)

In-order traversal = free sort

Visit the left subtree, then the node, then the right subtree - recursively. Because left holds everything smaller and right everything larger, an in-order walk emits values in ascending sorted order, for free, any time you like. Building a BST and reading it in-order is one way to sort; it is also why a BST doubles as an always-sorted, dynamically-updatable index.

Balance is not optional - it is the whole game

The $O (lo g n)$ promise depends entirely on the tree staying bushy. Insert already-sorted data - 10, 20, 30, 40, 50, 60 - and every new value is larger than everything before it, so it goes right, right, right... The tree becomes a linked list of height $n - 1$ , and search decays to $O (n)$ .

balanced h \approx lo g_{2} n \Rightarrow O (lo g n) vs. skewed h = n - 1 \Rightarrow O (n) .

The fix is self-balancing trees - AVL and red-black trees - which perform tiny local rotations after each insert to keep the height near $lo g_{2} n$ no matter what order the data arrives in. We tease that in a later lesson; for now, just internalize why it is needed.

Traversals & the insert code

There are four canonical ways to visit every node. The first three are recursive and differ only in when you touch the node relative to its children; the fourth sweeps level by level.

Traversal	Order	Typical use
Pre-order	node, left, right	Copy or serialize a tree
In-order	left, node, right	Sorted output from a BST
Post-order	left, right, node	Delete / free, evaluate expression trees
Level-order	top to bottom rows	Breadth-first / shortest hops (a queue)

Insert and in-order fall straight out of the invariant - both are three-line recursions:

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

def insert(root, val):
    if root is None:
        return Node(val)                     # empty slot -> new leaf
    if val < root.val:
        root.left  = insert(root.left,  val)    # smaller -> go left
    elif val > root.val:
        root.right = insert(root.right, val)    # larger  -> go right
    return root                              # equal   -> ignore duplicate

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)  # sorted!

Check yourself

In a binary search tree, where do all values in a node's left subtree sit relative to that node?

What happens to a plain BST's height when you insert already-sorted values one by one?

Recall: which traversal of a BST outputs values in sorted order, and why?

Tie the traversal order back to the invariant. Try to state it, then check.

Lock it in

A BST holds one invariant at every node - smaller values left, larger values right - so search, insert, and delete are repeated binary decisions costing $O (h)$ .
Balanced, $h \approx lo g_{2} n$ gives $O (lo g n)$ ; insert already-sorted data and it decays into a linked list of height $n - 1$ , $O (n)$ - which is why self-balancing trees exist.
An in-order traversal (left, node, right) emits values in sorted order for free, so a BST doubles as an always-sorted, updatable index.
Four traversals: pre-order (copy/serialize), in-order (sorted output), post-order (delete/evaluate), and level-order (breadth-first via a queue).

Primary source

Build and break your own trees with the two classic visualizers: VisuAlgo - Binary Search Tree animates insert, search, and traversals step by step, and the USF Data Structure Visualizations (David Galles) let you watch AVL and red-black rotations kick in the moment a tree starts to skew.

Ask your teacher

Want to see how a delete works when the node has two children, or how a single rotation restores balance? Ask me and we'll trace it. And the tie to the LLM path is closer than it looks: beam search explores a tree of partial sequences when decoding text, and a trie - itself a tree - powers the tokenizer that turns your text into tokens. Trees are how both paths organize hierarchical search.