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.