Trees & Binary Search Trees

A tree models hierarchical relationships, and a Binary Search Tree (BST) lets us find data in O(log n) time — but only when the tree is balanced. Otherwise it degrades to O(n), and the entire reason we reached for a tree instead of a plain list evaporates.

Core idea

A tree is a hierarchical data structure made of nodes connected by edges, with no cycles. Key terms:

• root — the topmost node, with no parent
• node — a unit that stores a value and points to its children
• edge — the connection between a node and its child
• parent / child — a node directly above/beneath another node
• sibling — nodes that share the same parent
• ancestor / descendant — any node above/below a given node along the path to the root
• leaf — a node with no children at all
• subtree — a node together with all of its descendants, viewed as its own tree
• depth — the number of edges from the root down to a given node
• height — the number of edges on the longest path from a node down to a leaf (the height of the whole tree = height of the root)
• degree — the number of children a node has

A binary tree is a tree where every node has at most 2 children, called the left child and the right child.

        8          <- root
       / \
      3   10
     / \    \
    1   6    14    <- 14 is a leaf
       / \
      4   7        <- height = 3

This hierarchical structure is everywhere: from your file system, to the HTML structure of a web page, to an organization’s chain of command.

Shapes of binary trees

Not all binary trees look the same, and the shape affects performance. Three shapes come up constantly in interviews and in real libraries:

Shape	Definition	Why it matters
Full	Every node has 0 or 2 children (never exactly 1)	Common invariant for expression trees
Complete	Every level is fully filled except possibly the last, which fills left-to-right	Lets you store the tree in a flat array with no wasted gaps — this is exactly what a heap relies on
Perfect	Every level is completely filled	Guarantees height = log2(n) exactly; used as the “best case” reference shape

Keep “complete” in mind — it resurfaces later when we talk about heaps.

The BST property

A binary search tree adds one rule to an ordinary binary tree:

For every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater than it — in short, left < node < right. This must hold for every subtree, not just the immediate children.

This rule matters because it lets us search by “halving” like binary search: start at the root; if the target is less than the node, go left; if greater, go right. Each step throws away half of the remaining data, so when the tree is balanced the number of steps is O(log n).

A beautiful side effect: an in-order traversal (left → node → right) of a BST always yields the values sorted in ascending order.

Worked example: searching for a value

Using the tree above, let’s trace two searches step by step.

Search for 7 (found):

Step	Current node	Comparison	Move
1	8	7 < 8	go left
2	3	7 > 3	go right
3	6	7 > 6	go right
4	7	7 == 7	found, 4 steps

Search for 11 (not found):

Step	Current node	Comparison	Move
1	8	11 > 8	go right
2	10	11 > 10	go right
3	14	11 < 14	go left
4	None	—	not found, 3 comparisons then a null child

Notice that an unsuccessful search still only takes O(h) steps (h = height) — it just terminates at an empty spot instead of a match.

Traversals

A traversal visits every node systematically. There are three main depth-first traversals for binary trees, differing in when they visit the node itself relative to its children:

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

def preorder(node):    # node -> left -> right
    if node is None:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

def inorder(node):     # left -> node -> right  (sorted output for a BST)
    if node is None:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

def postorder(node):   # left -> right -> node
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

• pre-order — good for “copying” or reconstructing a tree, and for serializing its structure
• in-order — for a BST, produces sorted values; great for ordered display
• post-order — visits children before the parent; good for “deleting” a tree bottom-up, or evaluating an expression tree (compute the children’s values before combining them at the parent)

Worked example: three traversals of one tree

Using the same tree (root 8), here is what each traversal visits, in order:

Traversal	Output sequence
pre-order	8, 3, 1, 6, 4, 7, 10, 14
in-order	1, 3, 4, 6, 7, 8, 10, 14
post-order	1, 4, 7, 6, 3, 14, 10, 8

Notice in-order gives a perfectly sorted list — that’s the BST property paying off directly.

The widget above animates fib(n)’s call tree, not a traversal — but the mental model transfers directly. Every traversal call (inorder(node.left), inorder(node.right)) is itself a new stack frame that must fully return before its parent continues. Watch how the fib calls branch, recurse to the bottom, and unwind — that “branch down, then unwind” rhythm is exactly what inorder(8) does: it dives all the way down the left spine before it ever prints anything.

Level-order traversal (BFS)

The three traversals above are all depth-first — they plunge down one branch before backtracking. Sometimes you want to visit nodes level by level instead (top row, then the next row, and so on). That’s breadth-first search (BFS), implemented with a queue instead of recursion:

from collections import deque

def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

Level-order is what you want for: printing a tree row by row, finding the width of each level, or serializing a tree in a way that’s easy to reconstruct breadth-first.

Worked example — queue trace for the same tree:

Step	Dequeue	Visit order so far	Enqueue
1	8	8	3, 10
2	3	8, 3	1, 6
3	10	8, 3, 10	14
4	1	8, 3, 10, 1	—
5	6	8, 3, 10, 1, 6	4, 7
6	14	8, 3, 10, 1, 6, 14	—
7	4	8, 3, 10, 1, 6, 14, 4	—
8	7	8, 3, 10, 1, 6, 14, 4, 7	—

Final output: 8, 3, 10, 1, 6, 14, 4, 7 — top level first, then left-to-right across each row.

Insert and search

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

def search(node, val):
    if node is None or node.val == val:
        return node
    if val < node.val:
        return search(node.left, val)
    return search(node.right, val)

Both functions do the exact same “compare, then go left or right” walk as the search example above — insertion is really just “search for where this value would be, then place it there.”

Worked example: building a BST from scratch

Insert 50, 30, 70, 20, 40, 60, 80 into an empty tree, one at a time:

Insert	Path taken	Lands at
50	(empty)	becomes root
30	30 < 50, go left	left child of 50
70	70 > 50, go right	right child of 50
20	20 < 50 → 20 < 30, go left, go left	left child of 30
40	40 < 50 → 40 > 30, go left, go right	right child of 30
60	60 > 50 → 60 < 70, go right, go left	left child of 70
80	80 > 50 → 80 > 70, go right, go right	right child of 70

Result — a perfectly balanced tree of height 2 for 7 nodes:

        50
       /  \
      30    70
     / \   / \
    20 40 60 80

This is what a BST looks like when insertion order is “friendly” (roughly random / balanced). Later we’ll see what happens when it isn’t.

Delete

Deletion is the trickiest BST operation because removing a node must not break the left < node < right invariant. There are three cases:

1. Node is a leaf — just remove it, its parent’s pointer becomes None.
2. Node has one child — splice it out: the parent now points directly at the node’s only child.
3. Node has two children — you cannot simply remove it without leaving a gap. Instead, find its in-order successor (the smallest value in its right subtree — reached by walking right, then left, left, left...), copy that value into the node being “deleted,” then recursively delete the successor from the right subtree (where it’s guaranteed to have at most one child, reducing to case 1 or 2).

def delete(node, key):
    if node is None:
        return None
    if key < node.val:
        node.left = delete(node.left, key)
    elif key > node.val:
        node.right = delete(node.right, key)
    else:
        # found the node to delete
        if node.left is None:
            return node.right          # case 1 or 2
        if node.right is None:
            return node.left           # case 2
        # case 3: two children — replace with in-order successor
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.val = successor.val
        node.right = delete(node.right, successor.val)
    return node

Worked example: deleting a node with two children

Using the same tree as above (root 8), delete 3. Node 3 has two children (1 and 6), so we’re in case 3:

1. Find the in-order successor of 3: go to its right subtree (rooted at 6), then keep going left. 6 has a left child 4, and 4 has no left child, so the successor is 4.
2. Copy 4 into the node currently holding 3.
3. Recursively delete the original 4 from the right subtree — 4 is a leaf, so it’s simply removed.

before:              after deleting 3:
        8                    8
       / \                  / \
      3   10                4   10
     / \    \      ->      / \    \
    1   6    14           1   6    14
       / \                     \
      4   7                     7

Node 4 now sits where 3 used to be, and its old spot under 6 is gone. The BST property still holds everywhere.

Balance matters

The O(log n) speed of a BST is not always guaranteed. Look at what happens when we insert already-sorted data such as 1, 2, 3, 4, 5 (contrast this with the friendly 50, 30, 70, ... order from the insert example above):

    1
     \
      2
       \
        3
         \
          4
           \
            5    <- height = n

Every new value is greater than the previous one, so it always goes to the right. The tree degenerates into a “linked list” with height equal to n. Search must now walk node by node, becoming O(n) — losing the tree’s entire advantage.

This is the key trap: a plain BST is fast only “on average” with randomly distributed data, but its worst case is O(n).

The fix — self-balancing trees. Structures like the AVL tree and the red-black tree add extra bookkeeping (a stored height or a node “color”) and, after every insert or delete, check whether the tree has become lopsided. If it has, they perform a rotation — a local restructuring of a few pointers that swaps a node with one of its children while preserving the BST ordering — to restore balance. AVL trees rebalance aggressively (height difference between subtrees never exceeds 1, giving very fast lookups but more rotations on writes); red-black trees are looser (a weaker balance invariant enforced via node coloring) but need fewer rotations on average, which is why they back most language standard libraries (e.g., C++’s std::map, Java’s TreeMap). Either way, the guarantee is the same: height stays O(log n) no matter what order you insert in. (The rotation mechanics are an advanced topic — for now, just know why they exist: to defeat exactly the degeneration shown above.)

Where heaps fit in. A heap is a different tree-based structure that is easy to confuse with a BST because it’s also usually drawn as a binary tree — but it enforces a much weaker rule: the heap property (every parent is ≤ its children, for a min-heap, or ≥ for a max-heap) — not the full left/right ordering of a BST. Because a heap only cares about parent-child order and is always kept as a complete binary tree (that “shape” concept from earlier), it can be packed into a flat array with no pointers at all, and its one specialty — instantly finding the min or max, and removing it in O(log n) — makes it the natural engine behind priority queues, heapq in Python, Dijkstra’s algorithm, and OS task schedulers. The trade-off: a heap cannot do a general O(log n) search for an arbitrary value (that requires the full BST ordering) — it’s a specialist for “give me the smallest/largest,” while a BST is a generalist for “keep everything sorted and searchable.”

Complexity

Operation	Balanced BST	Unbalanced BST (worst case)
search	O(log n)	O(n)
insert	O(log n)	O(n)
delete	O(log n)	O(n)
full traversal (any order)	O(n)	O(n)
space (recursion stack depth)	O(log n)	O(n)

The difference in search/insert/delete comes purely from the tree’s “height”: every one of those operations costs as much as the height — O(log n) for a balanced tree, up to O(n) for a skewed one. A full traversal always visits every node once, so it’s O(n) regardless of balance — but a skewed tree also costs O(n) of recursion-stack space, versus O(log n) for a balanced one.

Real-world problem: ordered index and range queries

Think of an autocomplete system or a sorted database index. When a user types “ad”, we want to quickly return all words in the range ["ad", "ae").

If we store the data in an unsorted flat list, finding a range means scanning every element = O(n) each time. But with a balanced BST (or its relatives that real databases use):

• find the start of the range in O(log n)
• then continue an in-order traversal to pull out the values in the range, in order

This is why a database index (such as a B-tree, which extends the BST idea) performs range queries far faster than scanning an entire table. The tree keeps data ordered at all times, so it answers “greater-than / less-than / between” questions efficiently. (Contrast this with the heap use case above: a database index needs ordered range access, so it reaches for a balanced BST variant, not a heap — a heap would happily tell you the single smallest row, but not “give me every row between ‘ad’ and ‘ae’.”)

Exercises

1. Predict the search path Using the tree from the Core idea section (root = 8), write the sequence of nodes visited when searching for the value 7.

Answer

8 → 3 → 6 → 7 Start at 8 (7 < 8, go left) → 3 (7 > 3, go right) → 6 (7 > 6, go right) → 7 found. Four steps.

2. Insert in order, then draw the tree Insert the values 5, 2, 8, 1, 3 into an empty BST in this order, then draw the resulting tree.

Answer

      5
     / \
    2   8
   / \
  1   3

5 becomes the root, 2 < 5 goes left, 8 > 5 goes right, 1 < 5 < 2 goes left of 2, 3 < 5 but > 2 goes right of 2.

3. Validate a BST Is the following tree a valid BST? Why or why not?

      10
     /  \
    5    15
        /  \
       6    20

Answer

No, it is not a valid BST. Node 6 sits in the right subtree of 10, so every value there must be greater than 10 — but 6 < 10, violating the rule. Watch out: validating requires tracking the allowed value range for an entire subtree, not just comparing against the immediate parent.

4. Find min and max In any BST, where are the minimum and maximum values located, and how do you walk to them?

Answer

• minimum: keep going left until there is no left child
• maximum: keep going right until there is no right child

Both take O(h) where h is the height (so O(log n) when balanced). This is exactly the walk the delete function uses to find an in-order successor.

5. What does in-order give? If you traverse the tree from Exercise 2 in in-order, what sequence do you get?

Answer

1, 2, 3, 5, 8 — sorted ascending, by the BST property.

6. What does level-order give? Using the same tree from Exercise 2 (root 5), what sequence does a level-order (BFS) traversal produce?

Answer

5, 2, 8, 1, 3 — root first, then left-to-right across the next level, then the level after that. Compare this with the in-order result (1, 2, 3, 5, 8) — same tree, completely different order, because BFS visits by depth while in-order visits by value position.

7. Delete a node with two children Using the tree from the Core idea section (root 8), what does the tree look like after deleting the root (8), which has two children (3 and 10)?

Answer

The in-order successor of 8 is the minimum of its right subtree (rooted at 10). 10 has no left child, so 10 is the successor. Copy 10 into the root, then delete the original node 10 from the right subtree — it has only a right child (14), so it’s spliced out and replaced by 14.

        10
       /  \
      3    14
     / \
    1   6
       / \
      4   7

8. Spot the bug An AI wrote this search function. It compiles and mostly seems to work in casual testing. What’s wrong with it, and for which inputs does it fail?

def search(node, val):
    if node is None:
        return None
    if val < node.val:
        return search(node.left, val)
    else:
        return search(node.right, val)

Answer

The bug: there is no check for val == node.val. When the target equals the current node’s value, the code falls into the else branch and recurses into the right subtree — but by the BST property, the right subtree contains only values greater than node.val, so the target can never be found there. The function returns None (search miss) even when the value exists in the tree, right at the node it just walked past.

Fix: add an explicit equality check before the comparisons:

def search(node, val):
    if node is None or node.val == val:
        return node
    if val < node.val:
        return search(node.left, val)
    return search(node.right, val)

AI Code Critique

Prompt given to the AI: “Write me a BST class in Python and tell me the time complexity of search.”

The AI’s answer: a plain BST class (insert/search as shown earlier), plus the claim:

“Search in my tree is always O(log n), because a BST halves the data at every step.”

Judge — what’s wrong with this claim?

The claim is wrong because a plain (non-self-balancing) BST does not guarantee a height of O(log n).

Counterexample: insert already-sorted data such as 1, 2, 3, 4, 5. The tree skews entirely to the right and becomes a linked list of height n. Searching for 5 must walk through every node = O(n).

The correct statement: a plain BST is O(log n) on average with random data, but its worst case is O(n). To guarantee O(log n), you need a self-balancing tree such as an AVL or red-black tree.

Improve — don’t just assume balance, verify it:

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

def is_balanced(node):
    if node is None:
        return True
    left_h, right_h = height(node.left), height(node.right)
    return (
        abs(left_h - right_h) <= 1
        and is_balanced(node.left)
        and is_balanced(node.right)
    )

The improved answer stops asserting O(log n) unconditionally, adds a way to actually check whether a given tree is balanced, and calls out the fix if it might not be: if incoming data could arrive sorted (or nearly sorted), either shuffle it before inserting, or switch to a self-balancing structure (an AVL/red-black tree, or a library one like Python’s sortedcontainers) so the O(log n) guarantee holds unconditionally rather than “usually.”

🎮 Game Dev: the scene tree and quadtree

A game engine’s scene tree is a tree in exactly the sense of this lesson: nodes joined by parent-child edges, no cycles, and one extra rule layered on top — a parent’s transform (position, rotation, scale) composes down onto every descendant. Walking that tree with a depth-first traversal is how an engine like Godot answers “where is everything in the world” every frame. And when the world gets big, you trade the value-ordering trick of a BST for a spatial-ordering one: a quadtree, a tree that splits on geometry instead of </>.

Worked example: propagating transforms down a scene tree

A naive approach stores every entity’s absolute world position directly. Move the parent, and you must remember to manually update every child, grandchild, and great-grandchild — miss one, and a weapon floats away from the hand holding it. The fix a tree gives you: each node stores only a local offset relative to its parent, and a single preorder traversal recomputes every world position from the root down — move one node, and the traversal cascades the change to everything beneath it automatically.

class Node:
    def __init__(self, name, local_x, local_y, local_scale=1.0):
        self.name = name
        self.local_x = local_x
        self.local_y = local_y
        self.local_scale = local_scale
        self.children = []
        self.world_x = 0.0
        self.world_y = 0.0
        self.world_scale = 1.0

    def add_child(self, child):
        self.children.append(child)

def propagate_transform(node, parent_x=0.0, parent_y=0.0, parent_scale=1.0):
    # parent -> child: scale the local offset, then add the parent's world position
    node.world_scale = parent_scale * node.local_scale
    node.world_x = parent_x + node.local_x * parent_scale
    node.world_y = parent_y + node.local_y * parent_scale
    for child in node.children:              # preorder: visit node, then recurse into children
        propagate_transform(child, node.world_x, node.world_y, node.world_scale)

# build the hierarchy: Player -> Sprite, Camera, Weapon -> Muzzle
player = Node("Player", 100, 100)
sprite = Node("Sprite", 0, 0)
camera = Node("Camera", -200, 0)
weapon = Node("Weapon", 20, -10)
muzzle = Node("Muzzle", 15, 0)
weapon.add_child(muzzle)
for child in (sprite, camera, weapon):
    player.add_child(child)

propagate_transform(player)
print(muzzle.world_x, muzzle.world_y)        # 135.0 90.0

player.local_x, player.local_y = 300, 150    # move the player...
propagate_transform(player)                  # ...one traversal updates every descendant
print(muzzle.world_x, muzzle.world_y)        # 335.0 140.0

propagate_transform is a preorder traversal — visit the node, then recurse into its children — the same shape as preorder() earlier in this lesson, just accumulating a transform instead of printing a value.

The widget above animates the shape of any depth-first call tree: dive down the leftmost branch, unwind, move to the next branch. That’s exactly the call shape of propagate_transform walking Player → Weapon → Muzzle — Muzzle’s world position isn’t finished until the recursive call into it returns.

Figure: a scene tree — Player’s transform cascades down to Sprite, Camera, and Weapon, and Weapon’s cascades one level further, down to Muzzle.

Where the quadtree fits in. A scene tree orders parent/child relationships; a quadtree orders space. For broad-phase collision in a large open world, checking every pair among n entities is O(n²) — and most pairs aren’t even close to each other. A quadtree instead recursively splits a square region into four quadrants whenever a quadrant holds more entities than some threshold (say, 4), so a collision query only has to descend into the quadrant(s) that overlap an entity’s bounding box, compare against the handful of entities actually stored there, and skip the rest of the world without inspecting it at all — turning a global O(n²) sweep into something closer to O(n log n).

Game-dev exercises

1. Traversal order In what order does propagate_transform(player) visit the five nodes above?

Answer

Player, Sprite, Camera, Weapon, Muzzle — it’s a preorder traversal: visit the node, then loop over its children in order. Weapon is visited before its own child Muzzle is recursed into.

2. Depth and degree queries What is the depth of Muzzle in this hierarchy? What is the degree (number of children) of Weapon? Is Muzzle a leaf?

Answer

Depth of Muzzle = 2 (Player → Weapon is one edge, Weapon → Muzzle is a second). Weapon’s degree = 1 (only Muzzle). Yes, Muzzle is a leaf — degree 0.

3. Why does propagation “just work”? After player.local_x, player.local_y = 300, 150 and one call to propagate_transform(player), Muzzle’s world position updates correctly — but no code ever touches muzzle.local_x or muzzle.local_y. Why?

Answer

Because the traversal is guaranteed to visit a parent — and finish updating its world_x/world_y — before it recurses into that parent’s children. So Weapon’s world position is recomputed from Player’s new world position, and then Muzzle’s world position is recomputed from Weapon’s new world position. Only the local offsets stay fixed; the accumulated world values flow down the same path the traversal takes.

4. Quadtree vs. flat list A large open world holds 10,000 entities. Why is finding “every entity within 50 units of the player” faster with a quadtree than looping over the flat list of all 10,000?

Answer

A flat list needs O(n) distance checks — every entity, everywhere in the world, no matter how far away. A quadtree lets you descend only into the quadrant(s) that overlap the 50-unit query region; any quadrant that doesn’t overlap is skipped without inspecting a single entity inside it. The cost becomes proportional to how many entities live near that point in space, not to how many entities exist in the whole world.

Challenge problems

Challenge 1: don’t recompute what didn’t move. Calling propagate_transform on the whole tree every single frame is wasted work if 99% of nodes haven’t moved since the last frame. Sketch a scheme that skips recomputing a subtree unless something in it actually changed.

Approach

Give every node a dirty: bool flag. Whenever a node’s local transform changes, mark that node and every one of its descendants dirty (their world position now depends on a stale value further up the chain). On each frame, traverse the tree but only recompute a node’s world transform if it’s dirty; walk into children regardless, since a dirty ancestor forces a dirty subtree. After recomputing a node, clear its flag. This is the same idea Godot’s own Node2D/Node3D use internally (a “transform dirty” bit) to avoid redoing matrix math for parts of the tree that haven’t moved.

Challenge 2: quadtree insert. Sketch how you would implement insert(entity) for a quadtree node that has bounds (x, y, w, h) and a capacity (say, 4 entities per node before it must subdivide).

Approach

class QuadNode:
    def __init__(self, x, y, w, h, capacity=4):
        self.bounds = (x, y, w, h)
        self.capacity = capacity
        self.entities = []
        self.children = None   # becomes a list of 4 QuadNodes once subdivided

    def insert(self, entity):
        if not self._overlaps(entity, self.bounds):
            return False
        if self.children is None and len(self.entities) < self.capacity:
            self.entities.append(entity)
            return True
        if self.children is None:
            self._subdivide()
        return any(child.insert(entity) for child in self.children)

_subdivide() splits self.bounds into four equal quadrants and creates a QuadNode for each; existing entities can be re-inserted into the new children. A query (e.g., “everything within radius r of point P”) walks the same tree, descending only into children whose bounds overlap the query circle — the same “skip whatever doesn’t overlap” trick used for collision in the paragraph above.

Going deeper

• MIT 6.006 Introduction to Algorithms — Binary Search Trees / AVL — lectures on BSTs and balanced trees
• Stanford CS161 — Design and Analysis of Algorithms — search trees and their analysis
• CLRS (Cormen et al.), Introduction to Algorithms, Chapter 12 — Binary Search Trees, and Chapter 13 — Red-Black Trees: the canonical rigorous treatment, including full rotation proofs
• Sedgewick & Wayne, Algorithms (4th ed.), Chapter 3.2–3.3 — clean Java implementations of BST insert/delete/traversal that lead directly into red-black BSTs in the same chapter
• Weiss, Data Structures and Algorithm Analysis — a careful, formula-driven treatment of tree height analysis and AVL rotation cases
• Goodrich, Tamassia & Goldwasser, Data Structures and Algorithms in Python — Python-native BST, AVL, and splay tree implementations you can read side by side with the code in this lesson
• VisuAlgo — Binary Search Tree — interactive visualization of BST operations