Graph Valid Tree

mediumTests passed 2026-11-11v1.0.0
TC: O(N * a(N))|SC: O(N)
GraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Graph theorem: an undirected graph on `n` vertices is a tree iff `len(edges) == n - 1` AND union-find joins all edges without ever seeing an internal cycle (`find(u) == find(v)`).

2. Complexity Bounds & Proof

Fail-fast `len(edges) != n - 1` rejects disconnected forests and multi-edge graphs immediately in O(1); verifying no cycles in `n - 1` unions proves 1 connected component.

3. Minimal Idiomatic Code

def validTree(n: int, edges: list[list[int]]) -> bool:
    if len(edges) != n - 1:
        return False
    parent = list(range(n))
    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False
        parent[rv] = ru
    return True

4. Failure Modes & Interview Follow-ups

Pitfalls:- Checking only cycle freedom passes disconnected forests like `[0-1, 2-3]` on `n=4` unless `len(edges) == n - 1` or `components == 1` is also enforced.
Follow-ups:- Rooted tree equivalence check via DFS passing `(node, parent)` instead of DSU.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Number of Connected Components in an Undirected Graph (O(V + E * a(V)))Course Schedule (O(V + E))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.