186. Validate an Undirected Tree

Why this mechanism works

A finite undirected tree has exactly n-1 edges. With that count established, connectivity is enough: a connected graph with a cycle would contain an extra edge beyond a spanning tree. Check the cheap edge count before building the adjacency list and traversing from vertex zero.

State and boundaries

seen contains vertices connected to zero through processed paths. The edge-count precheck fixes the only count compatible with a tree.

Protocol

1. Reject n=0 or an edge count other than n-1.
2. Build undirected adjacency.
3. Traverse from zero, marking on push.
4. Return whether all n vertices were reached.

Visualization

triangle 0-1-2-0 plus isolated 3
n=4, edges=3 passes n-1
only 3 reachable vertices -> reject

Python implementation

from kata_181 import adjacency_list

def valid_tree(n, edges):
    if n == 0 or len(edges) != n - 1:
        return False
    adj = adjacency_list(n, edges)
    seen, stack = {0}, [0]
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return len(seen) == n

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 valid_tree: if n == 0 or len(edges) != n - 1:
n=4; edges=[(0, 1), (1, 2), (1, 3)]

L6 valid_tree: adj = adjacency_list(n, edges)
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]

L7 valid_tree: seen, stack = {0}, [0]
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0}; stack=[0]

L9 valid_tree: u = stack.pop()
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0}; stack=[]; u=0

L10 valid_tree: for v in adj[u]:
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0}; stack=[]; u=0; v=1

L12 valid_tree: seen.add(v)
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0, 1}; stack=[]; u=0; v=1

L13 valid_tree: stack.append(v)
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0, 1}; stack=[1]; u=0; v=1

L9 valid_tree: u = stack.pop()
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0, 1}; stack=[]; u=1; v=1

... 6 intermediate state changes omitted ...

L13 valid_tree: stack.append(v)
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0, 1, 2, 3}; stack=[2, 3]; u=1; v=3

L9 valid_tree: u = stack.pop()
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0, 1, 2, 3}; stack=[2]; u=3; v=3

L10 valid_tree: for v in adj[u]:
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0, 1, 2, 3}; stack=[2]; u=3; v=1

L9 valid_tree: u = stack.pop()
n=4; edges=[(0, 1), (1, 2), (1, 3)]; adj=[[1], [0, 2, 3], [1], [1]]; seen={0, 1, 2, 3}; stack=[]; u=2; v=1

L4 valid_tree: if n == 0 or len(edges) != n - 1:
n=4; edges=[(0, 1), (1, 2), (2, 0)]

L6 valid_tree: adj = adjacency_list(n, edges)
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]

L7 valid_tree: seen, stack = {0}, [0]
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0}; stack=[0]

L9 valid_tree: u = stack.pop()
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0}; stack=[]; u=0

L10 valid_tree: for v in adj[u]:
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0}; stack=[]; u=0; v=1

L12 valid_tree: seen.add(v)
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0, 1}; stack=[]; u=0; v=1

L13 valid_tree: stack.append(v)
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0, 1}; stack=[1]; u=0; v=1

L10 valid_tree: for v in adj[u]:
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0, 1}; stack=[1]; u=0; v=2

... 3 intermediate state changes omitted ...

L10 valid_tree: for v in adj[u]:
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0, 1, 2}; stack=[1]; u=2; v=1

L10 valid_tree: for v in adj[u]:
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0, 1, 2}; stack=[1]; u=2; v=0

L9 valid_tree: u = stack.pop()
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0, 1, 2}; stack=[]; u=1; v=0

L10 valid_tree: for v in adj[u]:
n=4; edges=[(0, 1), (1, 2), (2, 0)]; adj=[[1, 2], [0, 2], [1, 0], []]; seen={0, 1, 2}; stack=[]; u=1; v=2

Why the solution is correct

Every tree passes the count and connectivity tests. Conversely, a connected graph on n vertices contains a spanning tree with n-1 edges. If the whole graph has only those many edges, none remain for a cycle, loop or parallel-edge cycle. Thus acceptance implies a tree.

Time and space

O(n+m) time and space after the count check; incompatible counts are rejected in O(1) when edges is a list.

Common mistakes

The n-1 count alone accepts a cyclic component plus an isolated vertex. Connectivity alone accepts graphs with extra cycle edges.

Reasoning card

Transfer exercise

Detect cycles during DFS with edge IDs rather than only a parent vertex, so parallel edges are handled correctly.