Trees and Prefix Structures

A child is the root of another tree

A binary tree has at most two children per node. It is not automatically a binary search tree. General graphs can contain cycles or shared nodes, so their traversal needs separate visited-state rules.

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

A tree can represent a document hierarchy or directory view. A real file system with symbolic links can introduce graph-like relationships; the model should state which edges are being traversed.

Balanced search-tree families constrain height so lookup remains logarithmic. AVL constrains local height differences; red-black trees enforce color/black-height rules instead. Red-black trees do not promise that every pair of child heights differs by at most one.

What should a subtree return?

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

A diameter is not the returned height. At a node with child heights L,R, a path joining the two sides has $L+R$ edges. Track the largest such candidate anywhere; return $1+\max(L,R)$ to the parent. Returning the global diameter instead would corrupt the parent's height calculation.

def diameter_of_binary_tree(root):
    diameter = 0
    def height(node):
        nonlocal diameter
        if node is None: return 0
        left = height(node.left)
        right = height(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)
    height(root)
    return diameter

For AVL-style balance checking, combine both child heights and their balance flags. A sentinel can encode failure, but its meaning must not be confused with a valid height. For maximum path sum, return the best single downward branch; a path joining both sides cannot continue upward without branching again.

When to record versus when to return

An iterative stack can express these orders too. To reproduce recursive return work, store a frame phase or push a separate exit event. A stack of nodes with only entry work does not automatically compute postorder child summaries.

Ancestor state flows downward

For path sums, pass the accumulated sum to each child. For nodes at least as large as every ancestor, pass the maximum seen on that root-to-node path; update it before entering the children. Root value or −∞ can initialize the maximum depending on the contract.

def count_good_nodes(root):
    def visit(node, path_max):
        if node is None: return 0
        good = int(node.value >= path_max)
        next_max = max(path_max, node.value)
        return good + visit(node.left, next_max) + visit(node.right, next_max)
    return visit(root, root.value) if root is not None else 0

Branch-local immutable arguments avoid one branch overwriting another's state. If a shared list stores the path, append before descent and pop after return. Copy only when recording an output that must survive later mutation.

Node depth counts edges from the root; subtree height counts remaining depth below the node. Name the convention, especially when the diameter or longest path uses edge counts.

A queue groups one depth at a time

Breadth-first search processes nodes by root distance. Capture the queue length before each level, then pop exactly that many nodes while appending their children. Otherwise the same loop can accidentally consume the next level too.

def level_order(root):
    from collections import deque
    if root is None: return []
    queue, result = deque([root]), []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            if node.left is not None: queue.append(node.left)
            if node.right is not None: queue.append(node.right)
        result.append(level)
    return result

The function returns complete level lists and imports deque itself. A binary-tree traversal visits n nodes in O(n) time. Recursive pending calls use O(h) space; BFS uses O(w) frontier space, where w is maximum level width. A skewed tree can make h=n.

BST order constrains entire subtrees

Under a distinct-key policy, every left-subtree value is below the node and every right-subtree value is above it. Checking only direct children misses a descendant that violates an ancestor's bound.

For example, root 10 with right child 15 and that child's left child 6 passes local child comparisons at 15 but violates root 10's right-subtree bound. Pass an open lower/upper interval down; every node must satisfy all inherited bounds.

A duplicate policy can instead permit equality on a specified side or store multiplicities at one node. Inorder is then nondecreasing, but the strict-bound validator must change. State the policy rather than mixing strict insertion with nonstrict validation.

Search, insertion and deletion cost O(h), not unconditionally O(log n). Balanced height makes that logarithmic. Random-input assumptions can produce an average-case statement; an arbitrary plain BST can become a chain.

The minimum is leftmost and maximum rightmost. A node with a right subtree has the right subtree's minimum as successor. Otherwise its successor is the first ancestor reached from a left branch; the maximum has none. Inorder selection finds the k-th key by traversal count, or subtree sizes can support rank/select.

An ancestor joins target evidence

In a general binary tree, a returned target or subtree candidate tells the parent which side contains evidence. One target from each child makes the current node the lowest common ancestor. If the current node is one target and the other is below it, the current node itself can be the answer.

The usual compact recursion assumes both targets exist. If existence is not guaranteed, also return presence counts/flags; otherwise one existing target may be incorrectly reported as a complete answer. Compare identity when distinct nodes can have equal values.

In a BST with known present distinct keys, both targets below or above the current value choose one branch. When they split—or one matches—the current node is their LCA. The ordering rule is an optimization of the same ancestor question.

Structure needs nulls or another contract

A preorder list of values alone does not determine an arbitrary binary tree. Include explicit null-child markers, or use another representation with enough structural information. Deserialization consumes tokens in the same order and validates premature endings and leftover data.

Distinct-valued preorder plus inorder can reconstruct a binary tree under their shared-node contract. Duplicates need more information. Do not infer uniqueness from a traversal that intentionally discarded structure.

Strings share prefix work

Each edge consumes one character and each node represents the consumed prefix. Exact lookup requires both reaching the node and seeing its terminal marker. Prefix lookup needs only a successful path.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
    def _find_node(self, text):
        node = self.root
        for char in text:
            if char not in node.children: return None
            node = node.children[char]
        return node
    def search(self, word):
        node = self._find_node(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        return self._find_node(prefix) is not None

The read-only _find_node method never creates nodes. Insertion creates missing edges and marks the final node terminal. A stored empty string marks the root. A word can be a prefix of another word, so a terminal node may still have children.

Insert/exact/prefix lookup takes O(L) character-edge operations under bounded child lookup cost. Memory follows stored prefix nodes, not simply the number of words. Sparse child maps save unused alphabet slots; fixed arrays trade that memory for direct access. Alphabet/normalization policies remain explicit.

root
├─ c ─ a ─ r* ─ t*
│       └─ t*
└─ d ─ o ─ g*

Wildcards and boards branch through prefixes

For an ordinary query character, follow its matching child. For a wildcard, explore every permitted child and succeed if one full query path ends at a terminal node. Search cost can grow with branching; it is not the exact lookup's O(L) guarantee.

def wildcard_search(root, word):
    def visit(index, node):
        if index == len(word): return node.is_word
        char = word[index]
        if char == '.':
            return any(visit(index + 1, child)
                       for child in node.children.values())
        if char not in node.children: return False
        return visit(index + 1, node.children[char])
    return visit(0, root)

Autocomplete walks the prefix once, then enumerates terminal descendants. Its cost includes output size. Terminal metadata can hold a word identifier, frequency or ranked candidate; storing complete strings at every internal node is often unnecessary.

For a board searched against many words, advance the trie alongside the board path. Reject a missing trie edge before further exploration. Mark a board cell used on the current path, then restore it on return. A global board visited set would incorrectly forbid reuse by a different starting path.

Emitting one terminal once can prevent duplicate output, but clearing its marker mutates the dictionary state. Restore or rebuild it if repeated queries must have the same behavior. Finding a shorter dictionary root can stop at the first terminal encountered during a word walk.

Choose the meaning of every piece of state

Before recursion, name the empty return value, the summary returned to a parent, the ancestor arguments and any global answer. Reset globals between independent calls. A traversal count, path state and subtree summary are not interchangeable.

Test empty and one-node trees, deep chains, broad levels, negative values, duplicate keys, an ancestor-bound violation and a missing LCA target. For tries, test a stored word that prefixes another, a prefix not inserted as a word, a missing edge and a wildcard that branches but never reaches a terminal.

Graph visited/frontier state → extends traversal to arbitrary connectivity. Dynamic Programming → shares the return-contract discipline but merges repeated logical states rather than assuming each subtree is unique.

Sources and related patterns

BST subtree order and rank operations ↗ · Prefix structures and wildcard branching ↗

Backtracking explains board-path ownership and restoring visited cells.