Trees as Graphs

A tree handed to you as n and an edge list is a different animal from a tree handed to you as a TreeNode with .left and .right. There is no root, no children, no parent pointers - just undirected edges, and the promise that there are exactly n - 1 of them with no cycle.

Everything on this page exploits that promise. Because a tree has exactly one path between any two vertices, questions that are hard on a general graph (longest path, distance between all pairs, "the best vertex to be the root") collapse to one or two linear passes.

Mnemonic

On a general graph, longest path is NP-hard. On a tree, it is two BFS calls. That gap is the reason it is worth checking len(edges) == n - 1 before reaching for anything heavier - it is an O(1) test that unlocks this entire page.

1. Rooting an undirected tree

The first move for most problems is to choose a root and impose the parent/child structure that a binary-tree problem would have handed you. It is one DFS, and the only mechanism needed is the parent-skip from Cycles & Ordering - a tree has no cycles, so refusing to walk back to your parent is the entire visited discipline required.

Same edge set, only the root differs - 'height' is only well-defined once a root is named.

def root_tree(n, edges, root=0):

adj = [[] for _ in range(n)]

for u, v in edges:

adj[u].append(v)

adj[v].append(u) # undirected: BOTH directions

 

parent = [-1] * n

depth = [0] * n

order = [] # a valid processing order (preorder)

stack = [root]

parent[root] = root # sentinel: the root is its own parent

while stack:

u = stack.pop()

order.append(u)

for v in adj[u]:

if v != parent[u]: # the ONLY guard a tree needs

parent[v] = u

depth[v] = depth[u] + 1

stack.append(v)

parent[root] = -1

return adj, parent, depth, order

Mnemonic

order reversed is a valid postorder. Because the preorder list appends a vertex before any of its descendants, walking reversed(order) guarantees every child is processed before its parent - which is exactly what a bottom-up tree DP needs, without recursion and without a stack-depth limit. This is the single most useful line on the page for large inputs.

⚠

Parent-skip by value breaks on multigraphs

Parent-skip by value breaks on a multigraph, and parent[root] needs a sentinel. Setting parent[root] = root before the loop stops the root from being re-entered through its own children; leaving it at -1 works only because no vertex is numbered -1, which silently fails the moment vertices are strings. And if the input can contain a duplicate edge, v != parent[u] skips both copies and the second one is lost - use an edge id if duplicates are possible (edge taxonomy).

2. Diameter: the two-BFS trick

The diameter of a tree is the longest path in it, measured in edges. On a general graph, finding the longest simple path is NP-hard. On a tree it is two traversals:

1. BFS (or DFS) from any vertex. Let u be a farthest vertex found.
2. BFS from u. Let v be a farthest vertex found. Then dist(u, v) is the diameter, and u -> v is a diameter path.

Sweep 1 from vertex 3 (arbitrary, not on the diameter) finds 6; sweep 2 from 6 finds the diameter. Badges show distance from 6.

from collections import deque

 

def tree_diameter(n, edges):

if n <= 1:

return 0

adj = [[] for _ in range(n)]

for u, v in edges:

adj[u].append(v)

adj[v].append(u)

 

def farthest(src):

dist = [-1] * n

dist[src] = 0

q = deque([src])

best = src

while q:

u = q.popleft()

if dist[u] > dist[best]:

best = u

for v in adj[u]:

if dist[v] == -1:

dist[v] = dist[u] + 1

q.append(v)

return best, dist[best]

 

u, _ = farthest(0) # sweep 1: from anywhere

v, d = farthest(u) # sweep 2: from a diameter endpoint

return d

Why an arbitrary start is good enough.

Take any vertex s and let u be the farthest vertex from it. If u were not an endpoint of any diameter, then the path from s towards the real diameter would have to reach the diameter at some vertex m - and from m, one of the two diameter ends is at least as far as u is, so swapping in that end gives a path at least as long through s. That contradicts u being the farthest. So u is always safe to sweep from, and the second sweep is the answer.

⚠

The double-sweep trick only works on trees

The double sweep is a tree theorem, and it silently gives wrong answers on a general graph. On a graph with a cycle, the farthest vertex from an arbitrary start is not necessarily on any diameter, and two BFS calls just return some path. Graph diameter needs BFS from every vertex - O(V * (V + E)). If the input might have a cycle, check len(edges) == n - 1 and connectivity first.

⚠

Double sweep needs non-negative weights

The double sweep works with non-negative weights but breaks with negative ones. Swap BFS for Dijkstra (or a weighted DFS) and the same two-sweep argument holds, because the proof only needs distances to satisfy the triangle inequality. Introduce a negative edge and there is no "farthest" to speak of.

The one-pass alternative

If you have already rooted the tree, the diameter falls out of a single postorder pass: at every vertex, the longest path through it is the sum of its two deepest child heights.

def tree_diameter_one_pass(n, adj, parent, order):

height = [0] * n # longest downward path from each vertex

best = 0

for u in reversed(order): # postorder: children before parents

top1 = top2 = 0

for v in adj[u]:

if v != parent[u]:

h = height[v] + 1

if h > top1:

top1, top2 = h, top1

elif h > top2:

top2 = h

height[u] = top1

best = max(best, top1 + top2) # the path bending AT u

return best

Mnemonic

Two sweeps or two heights. The double sweep needs no root and is easier to get right; the one-pass version needs a root but generalises - swap "two deepest heights" for any other combine and you have a tree DP. Use the double sweep to answer "what is the diameter"; use the one-pass shape when the diameter is a sub-question of something larger.

3. Center vs centroid

Two different "middle of the tree" notions that get confused constantly, because both are unique-ish and both are found in linear time.

	Center	Centroid
Minimises	the maximum distance to any vertex (the height if you root there)	the size of the largest remaining component after removing it (its mass balance)
Definition	the middle vertex (or two) of a diameter path	a vertex whose removal leaves every component with at most n/2 vertices
How many	1 or 2, always adjacent when 2	1 or 2, always adjacent when 2
Found by	peeling leaves layer by layer until 1 or 2 remain, or taking the midpoint of the diameter	computing subtree sizes, then walking towards the heaviest neighbour
Canonical use	LC 310 Minimum Height Trees - "which roots give the shortest tree"	centroid decomposition, and divide-and-conquer on trees

The center is the one that shows up in interviews, and the algorithm is memorable: it is Kahn's algorithm with degree 1 instead of in-degree 0.

from collections import deque

 

def tree_centers(n, edges):

if n <= 2:

return list(range(n))

adj = [[] for _ in range(n)]

degree = [0] * n

for u, v in edges:

adj[u].append(v)

adj[v].append(u)

degree[u] += 1

degree[v] += 1

 

leaves = deque(u for u in range(n) if degree[u] == 1)

remaining = n

while remaining > 2:

remaining -= len(leaves) # peel this ENTIRE layer

for _ in range(len(leaves)):

u = leaves.popleft()

for v in adj[u]:

degree[v] -= 1

if degree[v] == 1:

leaves.append(v)

return list(leaves)

Peeling leaves is walking inward from both ends of every diameter at once.

Each round strips one layer off every branch, so after k rounds the survivors are exactly the vertices at distance > k from every leaf. The last 1 or 2 standing are the middle of the longest path - which is the center by definition. There cannot be 3, because 3 mutually-adjacent survivors would be a cycle.

⚠

Peel one layer per round; guard n <= 2

Peel a whole layer per round, and handle n <= 2 before the loop. Popping one leaf at a time and re-checking remaining > 2 mid-layer strips branches unevenly and lands on the wrong vertex. And with n == 1 there are no degree-1 vertices at all, so the queue starts empty and the loop either never runs or spins - the early return is not optional.

⚠

Centroid isn't the center

The centroid is not the center, and "center of mass" is the right intuition. On a long path with a huge bushy blob at one end, the center sits at the midpoint of the longest path while the centroid sits inside the blob. If a problem says "minimise the height", it wants the center. If it says "split the tree into balanced pieces", it wants the centroid.

4. Distances and LCA

Because there is exactly one path between any two vertices, the distance between them decomposes through their lowest common ancestor (LCA) - the deepest vertex that is an ancestor of both:

$\text{dist}(u, v) = \text{depth}(u) + \text{depth}(v) - 2 \cdot \text{depth}(\text{lca}(u, v))$

For a handful of queries, walk both vertices up to equal depth and then step them up together - O(depth) per query. For many queries, binary lifting precomputes the 2^k-th ancestor of every vertex so each query is O(log n):

def build_lifting(n, parent, depth):

LOG = max(1, n.bit_length())

up = [[0] * n for _ in range(LOG)]

for v in range(n):

up[0][v] = parent[v] if parent[v] != -1 else v # root points at itself

for k in range(1, LOG):

for v in range(n):

up[k][v] = up[k - 1][up[k - 1][v]] # 2^k = 2^(k-1) twice

return up, LOG

 

def lca(u, v, up, LOG, depth):

if depth[u] < depth[v]:

u, v = v, u

diff = depth[u] - depth[v]

for k in range(LOG): # lift u to v's depth

if diff >> k & 1:

u = up[k][u]

if u == v:

return u # v was u's ancestor

for k in reversed(range(LOG)): # HIGHEST k first

if up[k][u] != up[k][v]:

u, v = up[k][u], up[k][v] # jump as high as is still safe

return up[0][u]

Binary lifting is binary search on depth, using the bits of the jump distance.

Lifting u by 13 levels is lifting by 8, then 4, then 1 - the set bits of 13. And the second loop is the same idea in reverse: from the largest jump down, take any jump that keeps the two vertices below their LCA. When no jump is safe, you are one step below it. The bit mechanics are the same ones on the bit-manipulation core page.

⚠

Binary lifting's inner loop must run high to low

The second loop must run from the highest k down, and its test is !=, not ==. Going low-to-high overshoots past the LCA and cannot come back. And the condition is deliberately conservative: you jump only while the two ancestors still differ, which keeps both strictly below the LCA, so the answer is up[0][u] afterwards - never u itself. Both mistakes return an ancestor that is too high, and both pass on a path-shaped tree.

⚠

A self-pointing up[k] is a sentinel, not a bug

A root whose up[k] points at itself is a deliberate sentinel, not a bug - but it must be a self-loop, not -1. Using -1 makes up[k-1][up[k-1][v]] index from the end of the list, silently producing garbage ancestors. Pointing the root at itself makes over-lifting saturate harmlessly at the root, which is exactly the behaviour the query loops rely on.

5. Tree DP, and rerooting

A tree DP is a postorder pass where each vertex combines its children's answers into its own. The shape is always the same; only the combine changes.

def max_weight_independent_set(n, adj, parent, order, weight):

# take[u] = best for u's subtree if u IS chosen (so no child may be)

# skip[u] = best for u's subtree if u is NOT chosen (children are free)

take = [0] * n

skip = [0] * n

for u in reversed(order): # children before parents

take[u] = weight[u]

for v in adj[u]:

if v != parent[u]:

take[u] += skip[v] # u chosen -> children skipped

skip[u] += max(take[v], skip[v]) # u skipped -> children free

root = order[0]

return max(take[root], skip[root])

That single template covers a large family: replace the combine and you get subtree sizes, subtree sums, counts of matching pairs, minimum vertex cover on a tree, maximum matching on a tree, and house-robber-on-a-tree. It is also why the NP-hard problems from Coloring & Covering become easy on a tree: there is a single well-defined "rest of the subtree" to defer to.

Rerooting: the answer for every root

Some problems ask for the answer with every vertex as the root - "sum of distances from each vertex to all others" (LC 834), "height of the tree rooted at each vertex". Running the DP n times is O(n^2). The rerooting technique gets all n answers in two passes:

1. Down pass (postorder): compute each vertex's answer over its own subtree.
2. Up pass (preorder): hand each child the answer for everything outside its subtree, which the parent can compute from its own total minus that child's contribution.

def sum_of_distances(n, adj, parent, order):

size = [1] * n

down = [0] * n # sum of distances within u's subtree

for u in reversed(order): # DOWN pass

for v in adj[u]:

if v != parent[u]:

size[u] += size[v]

down[u] += down[v] + size[v]

 

answer = [0] * n

answer[order[0]] = down[order[0]]

for u in order[1:]: # UP pass, parents before children

p = parent[u]

# step the root from p to u: everything outside u gets 1 farther,

# everything inside u gets 1 nearer

answer[u] = answer[p] + (n - size[u]) - size[u]

return answer

Rerooting is "what changes when I take one step?"

Moving the root from p to its child u moves you one step closer to the size[u] vertices inside u's subtree and one step farther from the other n - size[u]. So the answer shifts by exactly (n - size[u]) - size[u], and the whole second pass is that one line. Every rerooting problem is this question with a different delta.

⚠

Binary lifting's two passes run in opposite orders

The two passes go in opposite orders, and swapping them is silent. The down pass needs children first (reversed(order)); the up pass needs parents first (order), because answer[u] is derived from answer[parent[u]]. Run the up pass in reverse too and you read a parent's answer before it exists - which in Python is 0, not an error, so every answer comes out wrong by a plausible amount.

Where to go next

• Cycles & Ordering - the parent-skip and postorder mechanics this page leans on throughout.
• Coloring & Covering - the NP-hard set problems that the tree DP in section 5 makes linear.
• Binary trees - the same ideas when the input arrives as nodes with .left and .right instead of an edge list.