Trees

What it is

A tree is a connected graph without cycles. There is exactly one simple path between any two vertices. Rooting a tree gives each nonroot vertex one parent and partitions its descendants into disjoint child subtrees. Binary trees additionally distinguish left and right children.

These properties make recursive decomposition especially effective: solve each child subtree, then combine its result at the parent. Unlike a general graph, a tree needs no search over alternative routes between the same endpoints.

Tree techniques include traversal, path tracking, subtree dynamic programming, and rerooting. A traversal visits every node once. Subtree summaries avoid repeatedly scanning descendants, while rerooting can compute answers for every possible root without running a separate traversal from each one.

How to recognize it

Look for these signals:

• Nodes have child pointers, or the input is a connected graph with n - 1 edges.
• Output is grouped by depth or depends on the nearest level satisfying a condition.
• Conditions concern ancestors, descendants, leaves, or root-to-leaf paths.
• A parent's answer can be computed from answers for its children.
• Choices interact locally through parent-child edges or a bounded neighborhood.
• The objective concerns a longest path, selected vertices, subtree totals, or a connected subset.
• Distance-based answers are needed for every vertex, suggesting rerooting.

First establish whether edges are directed child links or undirected adjacency lists. For an undirected tree, pass the parent during traversal and skip that neighbor. If the input might contain cycles, parent skipping alone is insufficient; use visited tracking or validate the input.

The core technique

1. Breadth-first traversal: process one depth at a time

Use a queue when the answer depends on levels. At the beginning of each iteration, record the queue length. Exactly those nodes belong to the current depth; their children belong to the next depth.

from collections import deque

def levels(root):
    if root is None:
        return []
    queue = deque([root])
    result = []
    while queue:
        layer = []
        for _ in range(len(queue)):
            node = queue.popleft()
            layer.append(node.val)
            for child in (node.left, node.right):
                if child is not None:
                    queue.append(child)
        result.append(layer)
    return result

Keeping the layer boundary fixed prevents newly enqueued children from being processed at the wrong depth.

2. Depth-first traversal: carry context or return summaries

DFS has two complementary information flows:

• Top-down: pass ancestor information, such as a running sum or the previous value.
• Bottom-up: return information about a completed subtree, such as its total, height, or best path.

For a minimum root-to-leaf sum, accumulate values downward and consider an answer only at a leaf. An absent child is not a valid endpoint. Negative values also make pruning based only on the current sum unsafe.

def minimum_leaf_sum(root):
    if root is None:
        return None
    best = float('inf')

    def dfs(node, total):
        nonlocal best
        total += node.val
        if node.left is None and node.right is None:
            best = min(best, total)
            return
        for child in (node.left, node.right):
            if child is not None:
                dfs(child, total)

    dfs(root, 0)
    return best

To collect leaves whose entire path is strictly increasing, reject a child when its value is not greater than its parent's. Explore left before right to preserve leaf order. Pruning is valid because a later descendant cannot repair an already invalid path prefix.

For leaf-based aggregates, define a leaf's contribution, return the sum of child contributions, and compare each internal node's stored aggregate with that sum. Local parent-child equalities establish global consistency only when the leaf base cases are also correct.

3. Subtree dynamic programming: summarize boundary interactions

Use tree DP when a subtree needs several possible answers rather than one scalar. A state must describe everything the parent needs to know; information invisible outside the subtree can be discarded.

Common state patterns include:

• Selection and small budgets: track whether the subtree root is selected and how much budget is used. If selecting both endpoints consumes one unit, merging a child charges parent_selected and child_selected. Add child budgets and reject totals above the limit. This supports optimizing node weights under bounded parent-child interactions.
• Longest paths: store the best downward length for each allowed number of edge violations. A label change consumes one unit. At a node, combine arms from two distinct children, counting the node once and enforcing the total budget. Return only one arm upward because a simple path cannot branch.
• Bounded-radius coverage: track the nearest selected vertex and the farthest vertex still awaiting coverage. Retain an out-of-range distance sentinel. A selection in one child may cover an obligation in another through the parent, so merges must check cross-child distances. Pay a vertex's cost once when selecting it; at the root, reject remaining uncovered obligations.
• Exact-size connected subsets: let dp[k] represent the minimum cost of a connected set of size k containing the subtree root. Either exclude a child subtree or attach a connected child state containing that child. Merge sizes like knapsack. Signed vertex costs require retaining feasible states even when partial costs look unattractive. For boundary costs, an excluded child edge is charged while an included one becomes internal.

The general workflow is: define states, initialize leaves, merge children, then extract the root answer. Write the state meaning before the recurrence.

4. Rerooting and edge accounting

Rerooting uses one bottom-up pass followed by one top-down pass. For weighted distance sums, let sub[v] be the vertex-weight total below v, and total the whole-tree weight. Moving the root across an edge of length length makes distances to the child's subtree shorter and all others longer:

def propagate(u, parent):
    for v, length in adjacency[u]:
        if v == parent:
            continue
        answer[v] = answer[u] + length * (total - 2 * sub[v])
        propagate(v, u)

First compute subtree weights and the initial root's distance sum.

Unique paths also simplify walks visiting required vertices. Retain only branches leading to required vertices. A closed walk crosses each retained edge twice. An open walk starting at the root saves one traversal along its final root-to-endpoint path. Thus its minimum length is twice the retained edge-length total minus the greatest root distance to a required endpoint, assuming nonnegative edge lengths.

Common mistakes

• Treating missing children as leaves or defining leaves by undirected degree after rooting.
• Forgetting the parent check in adjacency-list DFS.
• Sharing mutable path state without undoing changes during backtracking.
• Combining two path arms from the same child.
• Omitting a boundary condition from a DP state.
• Initializing impossible minimization states to zero instead of infinity.
• Assuming Python recursion is safe for a long chain; use an explicit stack when necessary.

Complexity

Basic BFS and DFS take O(n) time because each vertex and edge is processed a constant number of times. BFS uses O(w) queue space for maximum width; recursive DFS uses O(h) stack space for height. Stored outputs add their own space.

Constant-state tree DP and rerooting usually take O(n) time and O(n) storage. With S states, naive child merges can cost O(nS²). Exact-size knapsack with limit K has a straightforward O(nK²) upper bound and O(nK) storage, often reduced by bounding each table by its subtree size.