Trees & Binary Search Trees

What a tree is, and the words for it

A tree is a collection of nodes connected by edges such that there is exactly one path between any two nodes. One node is the root; every other node has exactly one parent. Nodes with the same parent are siblings, and a node with no children is a leaf (the others are internal nodes). Because each node has one parent, a tree can never contain a cycle; that single fact is what makes recursion on trees so natural. Every child is itself the root of a smaller tree, its subtree.

Representing trees in Python

Python has no built-in tree type, so you choose a representation. The most flexible is a node class with references to children, exactly like the linked-list nodes from M21 but with two "next" pointers. A dataclass with slots=True keeps each node small.

Other representations trade flexibility for compactness:

tree = [8, 3, 10, 1, 6, None, 14]
left_of_3 = tree[2 * 1 + 1]   # 1

tree = (8, (3, (1, None, None), (6, None, None)), (10, None, (14, None, None)))

children = {"ceo": ["cto", "cfo"], "cto": ["dev1", "dev2"], "cfo": []}
parent = {c: p for p, kids in children.items() for c in kids}

What to remember: node objects for trees that change shape (BSTs, AVL trees); arrays for complete trees (heaps); dicts for named n-ary hierarchies.

Traversals: visiting every node

A traversal visits every node exactly once. Depth-first traversals differ only in when they process the current node relative to its subtrees:

• Pre-order (node, left, right): the node comes first. Use it to copy or serialize a tree, because a parent is written before its children.
• In-order (left, node, right): in a binary search tree this yields keys in sorted order.
• Post-order (left, right, node): children come first. Use it whenever a node's answer depends on its children's answers: heights, sizes, deleting a directory tree.

Step through a small traversal and watch the call stack grow to the tree's height, then shrink. The frames panel is the recursion's implicit stack.

Iterative versions with an explicit stack

Recursion depth equals tree height. On a degenerate tree with 5,000 nodes, Python's default recursion limit (about 1,000) is exceeded and you get RecursionError. Replacing the implicit call stack with an explicit list removes that limit, and the technique (simulate the call stack yourself) works for any recursive algorithm.

Level order with a queue

Level-order (breadth-first) traversal visits the root, then all depth-1 nodes, then depth 2, and so on. Swap the stack for a FIFO queue: collections.deque from M22. Processing one level at a time (by remembering the queue's length) gives you the levels as separate lists.

What to remember: pre-order for copying, in-order for sorted output, post-order when children answer first, level order for "by depth" questions. Recursion uses O(h) stack; iteration avoids the recursion limit.

Binary search trees: search and insert

A binary search tree (BST) is a binary tree with an ordering invariant, the BST property: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. Not just the children: the entire subtree. That invariant turns the tree into a decision procedure, the tree-shaped cousin of binary search: at each node, one comparison discards a whole subtree.

• Search: start at the root; go left if the key is smaller, right if larger; stop when equal or when you fall off the tree.
• Insert: search for the key; where the search falls off, attach a new leaf. New keys are always inserted as leaves.
• Min / max: keep going left (or right) until you cannot.

Each operation follows one root-to-leaf path, so it costs O(h). Insert values in the visualizer below, search for one, and run the traversals: in-order always comes out sorted.

Deleting from a BST: the three cases

Deletion is the operation people get wrong, because removing a node must leave the BST property intact. Find the node first, then:

1. Leaf: replace the parent's reference with None.
2. One child: replace the node with its only child. The child's whole subtree was already on the correct side of the parent, so the property holds.
3. Two children: find the in-order successor (go right once, then left as far as possible). It is the next larger key, so it can sit where the deleted node was: larger than everything on the left, smaller than everything else on the right. Copy its key up, then delete the successor from the right subtree; it has no left child, so that deletion is case 1 or 2. (The in-order predecessor works symmetrically.)

A recursive formulation is the cleanest: delete(node, key) returns the new root of the subtree, and each caller reattaches whatever comes back.

Degenerate trees and balancing

Every BST operation is O(h). The catch: h depends on insertion order. Insert 1, 2, 3, …, n into an empty BST and every new key goes to the right of the previous one. The "tree" is a linked list with height n − 1, and search is O(n). Sorted or nearly sorted input is common in practice (timestamps, auto-increment ids), so this is not a theoretical worry.

Random insertion gives expected height about 2.99 log₂ n, which is fine. Adversarial or sorted input does not. Self-balancing trees fix this by restructuring after each insert or delete so the height stays O(log n) no matter the order.

AVL trees and rotations

An AVL tree (Adelson-Velsky and Landis, 1962) stores each node's height and maintains the balance factor height(left) − height(right) in {−1, 0, 1}. After an insert, walk back up the path; at the first node whose balance factor becomes ±2, apply a rotation: a local pointer rearrangement that preserves the in-order sequence (so the BST property survives) while shortening the heavy side.

Insert 10, 20, 30, 40, 50 in the AVL-mode visualizer below and watch it rotate where a plain BST would grow a chain. Then try the same keys in the plain BST above.

Red-black trees and B-trees

Operation costs and Python's toolbox

Python's standard library has no balanced tree. In practice you reach for:

• dict / set when you only need exact lookups (O(1), from M23).
• A sorted list with bisect.insort and bisect_left when reads dominate: O(log n) search, and the O(n) insert is a fast memmove in C.
• heapq when you only need the minimum (next module).
• The third-party sortedcontainers package (SortedDict, SortedList) for a real ordered map. Add it with pixi add sortedcontainers.

Classic tree problems

Almost every tree problem is solved by one question: what does each node need from its children, and what does it return to its parent? Answer that and the recursion writes itself (usually post-order).

Serialization

To save a tree to a file or send it over a network, flatten it to a string. Pre-order with explicit markers for missing children (#) is unambiguous: the parent comes first, so rebuilding is a single recursive pass that consumes tokens from an iterator.

N-ary trees: file systems and Python's own syntax tree

Trees with any number of children are everywhere. A directory is a node whose children are files and directories; the HTML of this page is a tree of elements (the DOM); JSON is a tree of dicts and lists. Store children in a list (or a dict keyed by name), and the traversals generalize directly: pre-order visits a node then each child; post-order visits each child then the node.

Python itself parses your source into an abstract syntax tree before compiling it. The ast module exposes that tree; linters such as ruff and type checkers such as mypy are, at heart, tree walkers.

Practice

Each exercise defines a small Node class for you. Tests build trees and check your function.

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

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

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

from collections import deque

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

def inorder(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.key)
        node = node.right
    return out

def level_order(root):
    if root is None:
        return []
    out, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.key)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        out.append(level)
    return out

class Node:
    __slots__ = ("key", "left", "right")
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

class BSTSet:
    def __init__(self):
        self.root = None
        self._size = 0

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            self._size += 1
            return
        node = self.root
        while True:
            if key == node.key:
                return
            if key < node.key:
                if node.left is None:
                    node.left = Node(key)
                    self._size += 1
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = Node(key)
                    self._size += 1
                    return
                node = node.right

    def __contains__(self, key):
        node = self.root
        while node:
            if key == node.key:
                return True
            node = node.left if key < node.key else node.right
        return False

    def remove(self, key):
        self.root = self._remove(self.root, key)
        self._size -= 1

    def _remove(self, node, key):
        if node is None:
            raise KeyError(key)
        if key < node.key:
            node.left = self._remove(node.left, key)
        elif key > node.key:
            node.right = self._remove(node.right, key)
        else:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            succ = node.right
            while succ.left:
                succ = succ.left
            node.key = succ.key
            node.right = self._remove(node.right, succ.key)
        return node

    def __len__(self):
        return self._size

    def __iter__(self):
        stack, node = [], self.root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            yield node.key
            node = node.right

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

def is_bst(root, lo=float("-inf"), hi=float("inf")):
    if root is None:
        return True
    if not lo < root.key < hi:
        return False
    return is_bst(root.left, lo, root.key) and is_bst(root.right, root.key, hi)

def is_balanced(root):
    def check(node):
        if node is None:
            return -1
        left = check(node.left)
        if left == -2:
            return -2
        right = check(node.right)
        if right == -2 or abs(left - right) > 1:
            return -2
        return 1 + max(left, right)
    return check(root) != -2

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

def lca_bst(root, a, b):
    node = root
    while node:
        if a < node.key and b < node.key:
            node = node.left
        elif a > node.key and b > node.key:
            node = node.right
        else:
            return node.key
    return None

def serialize(root):
    out = []
    def walk(node):
        if node is None:
            out.append("#")
            return
        out.append(str(node.key))
        walk(node.left)
        walk(node.right)
    walk(root)
    return ",".join(out)

def deserialize(text):
    tokens = iter(text.split(","))
    def build():
        tok = next(tokens)
        if tok == "#":
            return None
        node = Node(int(tok))
        node.left = build()
        node.right = build()
        return node
    return build()

Mini-project: a BST-backed sorted map

pixi init treemap && cd treemap
pixi add python=3.14 pytest
pixi run python -m pytest -q

Quiz

Recap

• A tree has one root and exactly one path between any two nodes; every child roots a subtree, so recursion fits naturally.
• Depth counts edges up; height counts edges down. Balanced trees have height O(log n).
• Pre-order copies, in-order sorts (in a BST), post-order aggregates, level order groups by depth. Explicit stacks and queues replace recursion.
• The BST property is about whole subtrees. Search, insert, and delete cost O(h); deletion has three cases, and the two-child case uses the in-order successor.
• Sorted input makes a BST degenerate (O(n)). AVL and red-black trees rebalance with rotations to keep O(log n); B-trees go wide to minimize disk reads.
• Python has no built-in balanced tree: use dict, bisect on a sorted list, heapq, or sortedcontainers.

Going further

• bisect: array bisection algorithm
• ast: abstract syntax trees
• pathlib.Path.walk
• sortedcontainers documentation (and its essay on why it is not a tree)
• SQLite file format: B-tree pages
• Next: M25 Heaps & Priority Queues, a tree that lives in an array.