Trees, rooting and basic properties

A tree is a connected graph with no cycles. It has $N$ nodes and exactly $N-1$ edges. Every pair of nodes has exactly one unique path between them. This simple structure underpins many contest problems.

Unlike general graphs, trees are simpler to work with. You can root a tree at any node and process it recursively or iteratively. Parent-child relationships give you structure. You can compute distances between nodes in linear time. You can prune branches or find the longest path in $O(N)$.

Rooting a tree and parent arrays

To root a tree at a node, run BFS or DFS from that node and treat the traversal as a hierarchy. Each node's first visitor becomes its parent. Depth is the distance from the root.

1from collections import deque2
3
4def root_tree(adj, root):5    """Root a tree at a node, compute parent and depth."""6    n = len(adj)7    parent = [-1] * n8    depth = [-1] * n9    depth[root] = 010    queue = deque([root])11
12    while queue:13        u = queue.popleft()14        for v in adj[u]:15            if depth[v] == -1:16                depth[v] = depth[u] + 117                parent[v] = u18                queue.append(v)19
20    return parent, depth21
22
23adj = [24    [1, 2],25    [0, 3, 4],26    [0, 5],27    [1],28    [1],29    [2]30]31
32parent, depth = root_tree(adj, 0)33print("Parent:", parent)34print("Depth:", depth)

Parent: [-1, 0, 0, 1, 1, 2]
Depth: [0, 1, 1, 2, 2, 2]

The parent array lets you trace paths from any node to the root. The depth array shows how far each node is from the root. These arrays are building blocks for more complex algorithms.

Rooting matters because it transforms a tree from a symmetrical, undirected structure into a hierarchical one. Once rooted, you can ask questions like "is X an ancestor of Y?" by checking if you reach X while tracing Y's parent pointers toward the root. You can compute the lowest common ancestor (LCA) of two nodes by finding where their paths to the root meet. These capabilities are essential for tree DP and range-query problems.

Tree diameter: the longest path

The tree diameter is the longest path between any two nodes. Find it with two BFS passes: first from any node to find one end of the diameter, then from that end to find the farthest node.

1from collections import deque2
3
4def bfs_farthest(adj, start):5    """BFS from start, return (farthest_node, distance)."""6    n = len(adj)7    dist = [-1] * n8    dist[start] = 09    queue = deque([start])10    farthest = start11    max_dist = 012
13    while queue:14        u = queue.popleft()15        for v in adj[u]:16            if dist[v] == -1:17                dist[v] = dist[u] + 118                queue.append(v)19                if dist[v] > max_dist:20                    max_dist = dist[v]21                    farthest = v22
23    return farthest, max_dist24
25
26def tree_diameter(adj):27    """Find tree diameter using two BFS passes."""28    end1, _ = bfs_farthest(adj, 0)29    end2, diameter = bfs_farthest(adj, end1)30    return end1, end2, diameter31
32
33adj = [34    [1, 2],35    [0, 3],36    [0, 4, 5],37    [1],38    [2],39    [2]40]41
42end1, end2, diam = tree_diameter(adj)43print(f"Diameter endpoints: {end1}, {end2}")44print(f"Diameter: {diam}")

Diameter endpoints: 3, 4
Diameter: 4

This two-pass technique works because in a tree, one end of the diameter must be the farthest node from any starting point. The second pass finds the farthest node from that end, which is the other end of the diameter.

Diameter is useful when you need to know the longest distance between any two nodes in the tree. Some problems ask for the minimum distance you need to add to make all nodes close together, which uses diameter as a starting point. Others ask which nodes lie on the diameter path, which requires retracing the path using parent pointers after finding both ends.

Pruning leaves with a queue

Repeatedly removing leaves shrinks the tree. Use a queue: add all current leaves, remove them, and mark their parents as new leaves if they have degree 1 afterward. This processes the tree layer by layer from the outside in.

1from collections import deque2
3
4def prune_leaves(adj):5    """Prune leaves layer by layer."""6    n = len(adj)7    degree = [len(adj[i]) for i in range(n)]8    queue = deque([i for i in range(n) if degree[i] <= 1])9    layers = []10
11    while queue:12        layer = []13        for _ in range(len(queue)):14            u = queue.popleft()15            layer.append(u)16            for v in adj[u]:17                degree[v] -= 118                if degree[v] == 1:19                    queue.append(v)20        layers.append(layer)21
22    return layers23
24
25adj = [26    [1, 2],27    [0, 3, 4],28    [0, 5],29    [1],30    [1],31    [2]32]33
34layers = prune_leaves(adj)35for i, layer in enumerate(layers):36    print(f"Layer {i}: {layer}")

Layer 0: [3, 4, 5]
Layer 1: [1, 2]
Layer 2: [0]

Pruning is useful when you need to find the core of a tree or compute how many edges must be removed to satisfy some property.

Computing subtree aggregates

Often you need a value for each node that depends on its subtree: subtree size, maximum depth, sum of child values. Use postorder DFS to process children before parents.

1def compute_subtree_aggregates(adj, root):2    """Compute subtree size and max depth using postorder DFS."""3    n = len(adj)4    subtree_size = [0] * n5    max_depth = [0] * n6    visited = [False] * n7
8    def dfs(u):9        visited[u] = True10        subtree_size[u] = 111        max_depth[u] = 012
13        for v in adj[u]:14            if not visited[v]:15                dfs(v)16                subtree_size[u] += subtree_size[v]17                max_depth[u] = max(max_depth[u], max_depth[v] + 1)18
19    dfs(root)20    return subtree_size, max_depth21
22
23adj = [24    [1, 2],25    [0, 3, 4],26    [0, 5],27    [1],28    [1],29    [2]30]31
32size, depth = compute_subtree_aggregates(adj, 0)33print("Subtree sizes:", size)34print("Max depths:", depth)

Subtree sizes: [6, 3, 2, 1, 1, 1]
Max depths: [2, 1, 1, 0, 0, 0]

Postorder ensures that when you process a node, its children are already computed. You can then combine their results into the parent's value. This example recurses directly, which is fine on the small tree shown here. A tree with a long chain and a hundred thousand nodes needs the iterative marker technique from the previous module instead, since a recursive postorder DFS can still hit Python's recursion limit.

Why pruning matters

Pruning is used in problems where you need to remove nodes or edges under certain constraints. For example, a problem might say "remove all degree-1 vertices that don't have a certain property". Pruning layer by layer lets you remove these nodes efficiently. Start with all leaves, process them, and their former neighbors may become new leaves. This continues until either no more leaves exist or you have processed enough layers.

The queue-based approach ensures you process all current leaves before moving inward. This is much faster than repeatedly scanning for leaves, which would be $O(N^2)$ in a naive implementation.

A pruning example

Consider a tree where some nodes are marked as "important". You want to remove all unmarked leaves (nodes with degree 1 that are not important). Start by adding all unmarked degree-1 nodes to the queue. For each node removed, check its neighbors. If any become degree-1 and are unmarked, add them. Continue until the queue is empty. The remaining tree contains only marked nodes and paths between them. This takes $O(N)$ time because each node is added to the queue at most once.

Cost analysis

All tree algorithms discussed here run in $O(N)$ time where $N$ is the number of nodes. BFS or DFS visits each node once and each edge twice (once from each direction). Computing parent and depth arrays during rooting is part of the traversal. Pruning adds each node to the queue at most once, so it is also linear. Diameter requires two BFS passes, so $O(2N) = O(N)$. Subtree aggregates in postorder also visit each node once.

The space cost is $O(N)$ for the arrays and $O(\text{depth})$ for the stack or queue, which is at most $O(N)$ in the worst case (a chain). These linear costs make tree algorithms efficient even for $N = 10^6$.

Common mistakes

• Confusing tree diameter with depth: diameter is the longest path between any two nodes. Depth is the distance from the root to one specific node.
• Assuming edges are undirected: trees in contests are often given as undirected. Check that your adjacency list has an entry for both directions of each edge.
• Forgetting to mark the starting node: When doing DFS or BFS to root a tree, mark the root as visited first, or you will revisit it through its parent pointer.
• Integer overflow on large sums: If summing subtree values, use 64-bit integers. With $N = 10^6$ nodes and large weights, sums can exceed 32 bits.
• Off-by-one in parent arrays: After rooting a tree, the root's parent is -1 by convention. Check boundary conditions carefully when tracing paths to the root.

Recap

Trees have $N-1$ edges and unique paths between nodes. Rooting a tree gives parent-child structure. Diameter is found in $O(N)$ with two BFS passes. Leaves can be pruned layer by layer. Subtree aggregates are computed in postorder to process children before parents.