Graph Valid Tree

MEDIUM✓ CHIP-TIMEDLC #261 — FULL STATEMENT ↗

The drill: Given n nodes labeled 0 to n−1 and a list of undirected edges between them, decide whether the whole thing forms exactly one tree — every node reachable, and not a single extra edge creating a cycle.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A set of n nodes labeled 0 through n−1 arrives along with a list of undirected edges between them. The task is to decide whether those nodes and edges together form exactly one valid tree — nothing more, nothing less.

That means every node must be reachable from every other node through some path of edges, and there can't be a single extra edge anywhere creating a cycle or a shortcut between two nodes already connected.

A valid tree on n nodes always has exactly n−1 edges, but that count alone doesn't guarantee it — the edges also have to actually connect everything without looping back on themselves.

EX 01

n = 5 · edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

→ true

A STAR-SHAPED TREE

EX 02

n = 5 · edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]

→ false

ONE EXTRA EDGE CLOSES A CYCLE

EX 03

n = 1 · edges = []

→ true

A SINGLE NODE IS TRIVIALLY A TREE

up to a few thousand nodes and edges
edges are undirected and each pair of nodes appears at most once
a valid tree needs both zero cycles and full connectivity
answer is boolean — true only when both conditions hold together

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A tree on n nodes has exactly n−1 edges — any more and something cycles, any fewer and something is disconnected. That count alone is a free first check, but it's not sufficient by itself.

HINT 2 THE STRUCTURE

With exactly n−1 edges, the only way to fail is if two nodes that are already connected get a redundant edge between them, while some other pair stays unreachable. What single structure tracks "are these two already connected" as you add edges one at a time?

HINT 3 ONE STEP FROM THE ANSWER

Walk the edges with a disjoint-set: if two endpoints already share a root, that edge closes a cycle — fail immediately. If every edge merges two different sets and the edge count is exactly n−1, it's one tree.

COACH'S BOARD — THE PATTERN, STEP BY STEP

ONE PASS, ONE TREEPATTERN · UNION-FINDn = 5 · edges: (0,1) (0,2) (0,3) (1,4)

STEP 1

5 nodes, 4 edges — exactly n−1. That's necessary but not sufficient; union-find will confirm zero cycles as we merge.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/graph-valid-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            parent[ra] = rb

        return True

TIME O(V·Α(V))SPACE O(V)PYTHON · RACE PACE · 20 LN

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()

        def dfs(node, parent):
            visited.add(node)
            for nxt in graph[node]:
                if nxt == parent:
                    continue
                if nxt in visited:
                    return False
                if not dfs(nxt, node):
                    return False
            return True

        if not dfs(0, -1):
            return False
        return len(visited) == n

TIME O(V+E)SPACE O(V+E)PYTHON · TRAINING PACE · 26 LN

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;

        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] e : edges) {
            int ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra == rb) return false;
            parent[ra] = rb;
        }
        return true;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

TIME O(V·Α(V))SPACE O(V)JAVA · RACE PACE · 24 LN

class Solution {
    private Map<Integer, List<Integer>> graph;
    private Set<Integer> visited;

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;

        graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        visited = new HashSet<>();
        if (!dfs(0, -1)) return false;
        return visited.size() == n;
    }

    private boolean dfs(int node, int parent) {
        visited.add(node);
        for (int nxt : graph.get(node)) {
            if (nxt == parent) continue;
            if (visited.contains(nxt)) return false;
            if (!dfs(nxt, node)) return false;
        }
        return true;
    }
}

TIME O(V+E)SPACE O(V+E)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED