Trees, Traversals and BSTs: Why Balance Is the Only Thing Standing Between You and a Linked List

Heights, and why they are everything

A binary tree is nodes with up to two children. Its height \(h\) is the longest root-to-leaf edge count. With \(n\) nodes, \(h\) can be anywhere in

the lower bound because a tree of height \(h\) holds at most \(2^{h+1}-1\) nodes, the upper bound achieved by a path. Every search, insert and delete on a search tree walks one root-to-leaf path, so all of them are \(\Theta(h)\) — and which end of that range you are at is the entire question.

The four traversals

All four visit every node once, so all are \(\Theta(n)\) time. The depth-first three use \(\Theta(h)\) stack space; level-order uses \(\Theta(w)\) for the maximum level width \(w\), which is \(\Theta(n)\) in a balanced tree.

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(node, out):     # left, node, right
    if node:
        inorder(node.left, out); out.append(node.key); inorder(node.right, out)

def preorder(node, out):    # node, left, right
    if node:
        out.append(node.key); preorder(node.left, out); preorder(node.right, out)

def postorder(node, out):   # left, right, node
    if node:
        postorder(node.left, out); postorder(node.right, out); out.append(node.key)

def level_order(root):      # BFS, one queue
    out, q = [], deque([root] if root else [])
    while q:
        node = q.popleft()
        out.append(node.key)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

#        4
#      /   \
#     2     5
#    / \
#   1   3
root = Node(4, Node(2, Node(1), Node(3)), Node(5))

out = []; inorder(root, out);   print(out)   # [1, 2, 3, 4, 5]  -- sorted
out = []; preorder(root, out);  print(out)   # [4, 2, 1, 3, 5]
out = []; postorder(root, out); print(out)   # [1, 3, 2, 5, 4]
print(level_order(root))                     # [4, 2, 5, 1, 3]

Each has a job. Pre-order emits a parent before its children, so it is the serialisation order — replay it and you rebuild the same shape. In-order on a BST yields sorted keys, which is the cheapest correctness check you can run on one. Post-order finishes children first, so it is the traversal for anything computed from children: subtree sizes, heights, freeing memory, evaluating an expression tree. Level-order explores by depth, so it finds the shallowest node satisfying a predicate and gives you per-level output.

The BST invariant

Every key in a node’s left subtree is smaller than the node, every key in its right subtree is larger. The invariant is a contract about the whole subtree, not just the immediate children — checking only children is the classic wrong is_valid_bst.

The payoff: one comparison at a node discards an entire subtree. If the tree is balanced, that halves the candidates, giving \(\Theta(\log n)\) search. Insert descends to a leaf and attaches there. Delete is the fiddly one: a node with two children is replaced by its in-order successor (leftmost node of the right subtree), which is then deleted from its old position.

Nothing in the insert rule maintains balance, and that is the problem.

Self-balancing, stated as guarantees

You do not need the rotation cases in an interview; you need the contracts.

Both AVL and red-black restore their invariant with \(O(1)\) rotations per update, found on the way back up the insertion path. AVL is more strictly balanced, so lookups are marginally shorter; red-black does less restructuring work per update, which is why it backs most standard-library ordered maps (std::map, Java’s TreeMap) and the Linux kernel’s schedulers. B-trees widen the node so that one disk or page read covers many keys — the reason every relational database index is one.

Python ships no balanced tree. For ordered data use bisect on a sorted list (\(\Theta(\log n)\) search, \(\Theta(n)\) insert), or the third-party sortedcontainers. Most of the time a dict is the right answer, because you did not actually need order.

Tries

A trie keys on the path, not on comparisons: each edge is one character, so a word of length \(m\) costs \(\Theta(m)\) to look up regardless of how many words are stored. That is its selling point over a hash table, which also gives \(\Theta(m)\) to hash the string but cannot answer “all keys with this prefix” — a trie enumerates a prefix’s subtree directly. The cost is memory: a node per character per distinct prefix. Autocomplete, IP routing tables and subword tokeniser vocabularies are the usual applications.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022 — ch. 12 (BSTs) and 13 (red-black trees).
2. Adelson-Velsky, G. M., & Landis, E. M. An algorithm for the organization of information. Doklady Akademii Nauk SSSR 146, 263–266, 1962 — AVL trees.
3. Guibas, L. J., & Sedgewick, R. A dichromatic framework for balanced trees. 19th Annual Symposium on Foundations of Computer Science (FOCS), 8–21, 1978.
4. Bayer, R., & McCreight, E. Organization and maintenance of large ordered indices. Acta Informatica 1(3), 173–189, 1972 — B-trees.
5. Fredkin, E. Trie memory. Communications of the ACM 3(9), 490–499, 1960.
6. Python Software Foundation. bisect — Array bisection algorithm.
7. Jenks, G. sortedcontainers — pure-Python sorted list, dict and set.