261. Graph Valid Tree (Medium)

Problem

Given n nodes labeled 0 to n - 1 and a list of undirected edges, return true if the graph is a valid tree. A tree is connected and acyclic, which (given n nodes) means:

1. There are exactly n - 1 edges.
2. The graph is connected.
3. The graph has no cycle.

(1) and (3) together imply connectivity in practice, but interviewers may want both checked explicitly.

Example

• n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] → true
• n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] → false (cycle 1-2-3-1)

LeetCode 261 (premium, equivalent in 323 context) · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, DFS cycle + connected check

Build adjacency list. DFS from node 0 with parent tracking; if we reach a visited non-parent node, there’s a cycle. After DFS, verify every node was visited.

Python

from collections import defaultdict

def valid_tree(n, edges):
    if len(edges) != n - 1:                    # L1: O(1) early exit
        return False   # for trees, |E| = n - 1
    graph = defaultdict(list)                  # L2: adjacency list
    for u, v in edges:                         # L3: O(E) to build
        graph[u].append(v)                     # L4: O(1) per edge
        graph[v].append(u)                     # L5: O(1) per edge (undirected)

    visited = set()                            # L6: visited set
    def dfs(node, parent):                     # L7: recursive DFS
        if node in visited:                    # L8: cycle detected
            return False
        visited.add(node)                      # L9: O(1)
        for nb in graph[node]:                 # L10: visit neighbors
            if nb == parent:                   # L11: skip tree-parent edge
                continue
            if not dfs(nb, node):              # L12: recurse
                return False
        return True

    return dfs(0, -1) and len(visited) == n    # L13: connectivity check

TypeScript

function validTree(n: number, edges: number[][]): boolean {
    if (edges.length !== n - 1) return false;  // L1: O(1) early exit
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {              // L3: O(E) to build
        graph[u].push(v);                      // L4: O(1) per edge
        graph[v].push(u);                      // L5: O(1) per edge (undirected)
    }

    const visited = new Set<number>();         // L6: visited set
    function dfs(node: number, parent: number): boolean {
        if (visited.has(node)) return false;   // L8: cycle detected
        visited.add(node);                     // L9: O(1)
        for (const nb of graph[node]) {        // L10: visit neighbors
            if (nb === parent) continue;       // L11: skip tree-parent edge
            if (!dfs(nb, node)) return false;  // L12: recurse
        }
        return true;
    }

    return dfs(0, -1) && visited.size === n;   // L13: connectivity check
}

Go

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 { return false }        // L1: O(1) early exit
    graph := make([][]int, n)
    for _, e := range edges {                    // L3: O(E) to build
        graph[e[0]] = append(graph[e[0]], e[1]) // L4
        graph[e[1]] = append(graph[e[1]], e[0]) // L5
    }
    visited := map[int]bool{}                    // L6
    var dfs func(node, parent int) bool
    dfs = func(node, parent int) bool {
        if visited[node] { return false }        // L8: cycle detected
        visited[node] = true                     // L9
        for _, nb := range graph[node] {         // L10
            if nb == parent { continue }         // L11: skip parent edge
            if !dfs(nb, node) { return false }  // L12
        }
        return true
    }
    return dfs(0, -1) && len(visited) == n       // L13
}

Swift

final class Solution {
    func validTree(_ n: Int, _ edges: [[Int]]) -> Bool {
        guard edges.count == n - 1 else { return false }
        var graph = Array(repeating: [Int](), count: n)
        for edge in edges { graph[edge[0]].append(edge[1]); graph[edge[1]].append(edge[0]) }
        var seen = Set<Int>()
        func visit(_ node: Int, _ parent: Int) -> Bool {
            if seen.contains(node) { return false }
            seen.insert(node)
            for next in graph[node] where next != parent && !visit(next, node) { return false }
            return true
        }
        return visit(0, -1) && seen.count == n
    }
}

Where the time goes, line by line

Variables: V = n (number of nodes), E = len(edges).

Line	Per-call cost	Times executed	Contribution
L1 (edge count check)	$O(1)$	1	$O(1)$
L2-L5 (build graph)	$O(1)$ per edge	E	$O(E)$
L6 (visited set)	$O(1)$	1	$O(1)$
L10-L12 (neighbor traversal in DFS)	$O(1)$ per edge	E total	$O(V + E)$ ← dominates
L13 (len check)	$O(1)$	1	$O(1)$

Each node is visited at most once (L8 exits immediately on revisit), and each undirected edge is examined twice (once per endpoint). Total DFS work is $O(V + E)$. The L1 guard means we never reach $O(E)$ > $O(n)$ inputs.

Complexity

• Time: $O(V + E)$, driven by L10-L12 (each node and edge visited once).
• Space: $O(V + E)$ for the graph and recursion stack.

Approach 2: Union-Find (optimal, stops at first cycle)

For each edge, union the two endpoints. If any union finds them already in the same component, there’s a cycle.

Python

def valid_tree(n, edges):
    if len(edges) != n - 1:                    # L1: O(1) early exit
        return False
    parent = list(range(n))                    # L2: O(n) init

    def find(x):                               # L3: path-compressed find
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # L4: path halving, O(alpha(n)) amortized
            x = parent[x]                      # L5: move up
        return x

    for u, v in edges:                         # L6: O(E) edge loop
        ru, rv = find(u), find(v)              # L7: O(alpha(n)) each
        if ru == rv:                           # L8: same component = cycle
            return False
        parent[ru] = rv                        # L9: union, O(1)
    return True                                # L10: passed all edges, tree confirmed

TypeScript

function validTree(n: number, edges: number[][]): boolean {
    if (edges.length !== n - 1) return false;  // L1: O(1) early exit
    const parent = Array.from({ length: n }, (_, i) => i);  // L2: O(n) init

    function find(x: number): number {         // L3: path-compressed find
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];     // L4: path halving
            x = parent[x];                     // L5: move up
        }
        return x;
    }

    for (const [u, v] of edges) {              // L6: O(E) edge loop
        const ru = find(u), rv = find(v);      // L7: O(alpha(n)) each
        if (ru === rv) return false;            // L8: same component = cycle
        parent[ru] = rv;                       // L9: union, O(1)
    }
    return true;                               // L10: passed all edges, tree confirmed
}

Go

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 { return false }        // L1: O(1) early exit
    parent := make([]int, n)
    for i := range parent { parent[i] = i }     // L2: O(n) init

    var find func(x int) int
    find = func(x int) int {                     // L3: path-compressed find
        for parent[x] != x {
            parent[x] = parent[parent[x]]        // L4: path halving
            x = parent[x]                        // L5
        }
        return x
    }

    for _, e := range edges {                    // L6: O(E) edge loop
        ru, rv := find(e[0]), find(e[1])         // L7
        if ru == rv { return false }             // L8: cycle
        parent[ru] = rv                          // L9: union
    }
    return true                                  // L10
}

Swift

struct UnionFind {
    var parent: [Int]
    var rank: [Int]
    init(_ count: Int) { parent = Array(0..<count); rank = Array(repeating: 0, count: count) }
    mutating func find(_ value: Int) -> Int {
        if parent[value] != value { parent[value] = find(parent[value]) }
        return parent[value]
    }
    mutating func union(_ left: Int, _ right: Int) -> Bool {
        var a = find(left), b = find(right)
        if a == b { return false }
        if rank[a] < rank[b] { swap(&a, &b) }
        parent[b] = a
        if rank[a] == rank[b] { rank[a] += 1 }
        return true
    }
}

final class Solution {
    func validTree(_ n: Int, _ edges: [[Int]]) -> Bool {
        guard edges.count == n - 1 else { return false }
        var unionFind = UnionFind(n)
        return edges.allSatisfy { unionFind.union($0[0], $0[1]) }
    }
}

Where the time goes, line by line

Variables: V = n (number of nodes), E = len(edges).

Line	Per-call cost	Times executed	Contribution
L1 (edge count check)	$O(1)$	1	$O(1)$
L2 (init parent)	$O(n)$	1	$O(n)$
L6-L9 (edge loop with find + union)	$O(alpha(n)$) per edge	E	$O(n · alpha(n)$) ← dominates

Complexity

• Time: $O(n · alpha(n)$) ≈ $O(n)$, driven by L6-L9 (one find+union per edge).
• Space: $O(n)$ for the parent array.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
DFS cycle + visited check	$O(V + E)$	$O(V + E)$
BFS cycle + visited check	$O(V + E)$	$O(V + E)$
Union-Find	$O(n · alpha)$	$O(n)$

Union-Find is the shortest answer and generalizes to incremental graph construction. DFS/BFS are equivalent and often cleaner when you need to also walk the graph for other reasons.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_261.py and run.
# Uses Union-Find (Approach 2) as the canonical implementation.

def valid_tree(n, edges):
    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 u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False
        parent[ru] = rv
    return True

def _run_tests():
    # Example 1: valid tree
    assert valid_tree(5, [[0,1],[0,2],[0,3],[1,4]]) == True

    # Example 2: cycle present
    assert valid_tree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]) == False

    # Single node, no edges
    assert valid_tree(1, []) == True

    # Two nodes, one edge
    assert valid_tree(2, [[0, 1]]) == True

    # Two nodes, no edges (disconnected)
    assert valid_tree(2, []) == False

    # Too many edges (n edges instead of n-1)
    assert valid_tree(3, [[0,1],[1,2],[0,2]]) == False

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function validTree(n: number, edges: number[][]): boolean {
    if (edges.length !== n - 1) return false;
    const parent = Array.from({ length: n }, (_, i) => i);

    function find(x: number): number {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    for (const [u, v] of edges) {
        const ru = find(u), rv = find(v);
        if (ru === rv) return false;
        parent[ru] = rv;
    }
    return true;
}

console.assert(validTree(5, [[0,1],[0,2],[0,3],[1,4]]) === true);
console.assert(validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]) === false);
console.assert(validTree(1, []) === true);
console.assert(validTree(2, [[0,1]]) === true);
console.assert(validTree(2, []) === false);
console.assert(validTree(3, [[0,1],[1,2],[0,2]]) === false);
console.log("all tests pass");

Related data structures

• Graphs, tree detection via union-find or DFS

Related concepts

• Union Find, the component tracking structure for connectivity as edges are processed.
• Graph Traversal, the visited set model for exploring nodes and edges without repetition.