Graph Valid Tree (LC 261): Edge Count + BFS or Union-Find

Decide whether n nodes and a list of undirected edges form a valid tree: connected with no cycles. Solve LeetCode 261 with an edge-count check plus BFS, or with Union-Find in near-linear time.

Language Selection

Choose your preferred programming language

Showing: Python

Graph Valid Tree

Problem Statement

You have n nodes labeled 0 to n - 1 and a list edges, where each edges[i] = [a, b] is an undirected edge between nodes a and b. Return true if these edges make up a valid tree, and false otherwise.

A valid tree is a graph that is connected (every node can reach every other node) and has no cycles. Equivalently, it is a connected graph with exactly n - 1 edges.

Examples

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[1,3],[3,4]]
Output: true
Explanation: 4 edges connect all 5 nodes, and there is no cycle.
Node 1 is a hub joined to 0, 2 and 3, and 4 hangs off node 3.

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[2,0],[2,3]]
Output: false
Explanation: Nodes 0, 1 and 2 form a cycle. With 4 edges on 4 nodes,
there is one edge too many for a tree.

Example 3:

Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Explanation: There is no cycle, but {0,1} and {2,3} are separate pieces,
so the graph is not connected.

Constraints

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= a, b < n and a != b
  • No edge appears twice

Approach 1: Edge Count + BFS Connectivity Check

Algorithm

A graph with n nodes is a tree exactly when it has n - 1 edges and it is connected. (A connected graph with n - 1 edges cannot contain a cycle, because removing a cycle edge would leave a connected graph with only n - 2 edges, which is impossible.) So you never need to detect cycles directly.

  1. If len(edges) != n - 1, return false. Too many edges means a cycle; too few means the graph is disconnected.
  2. Build an adjacency list.
  3. BFS from node 0, marking nodes as visited.
  4. Return true if the BFS visited all n nodes.

Implementation

Python:

from collections import deque
from typing import List


class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # a tree on n nodes has exactly n - 1 edges
        if len(edges) != n - 1:
            return False

        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        # with n - 1 edges, the graph is a tree iff it is connected
        seen = [False] * n
        seen[0] = True
        queue = deque([0])
        visited = 1
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if not seen[nxt]:
                    seen[nxt] = True
                    visited += 1
                    queue.append(nxt)
        return visited == n

Java:

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // a tree on n nodes has exactly n - 1 edges
        if (edges.length != n - 1) return false;

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

        // with n - 1 edges, the graph is a tree iff it is connected
        boolean[] seen = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        seen[0] = true;
        queue.add(0);
        int visited = 1;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : graph.get(node)) {
                if (!seen[next]) {
                    seen[next] = true;
                    visited++;
                    queue.add(next);
                }
            }
        }
        return visited == n;
    }
}

Go:

func validTree(n int, edges [][]int) bool {
    // a tree on n nodes has exactly n - 1 edges
    if len(edges) != n-1 {
        return false
    }

    graph := make([][]int, n)
    for _, e := range edges {
        graph[e[0]] = append(graph[e[0]], e[1])
        graph[e[1]] = append(graph[e[1]], e[0])
    }

    // with n - 1 edges, the graph is a tree iff it is connected
    seen := make([]bool, n)
    seen[0] = true
    queue := []int{0}
    for head := 0; head < len(queue); head++ {
        for _, next := range graph[queue[head]] {
            if !seen[next] {
                seen[next] = true
                queue = append(queue, next)
            }
        }
    }
    return len(queue) == n // every node was enqueued exactly once
}

JavaScript:

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function (n, edges) {
    // a tree on n nodes has exactly n - 1 edges
    if (edges.length !== n - 1) return false;

    const graph = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }

    // with n - 1 edges, the graph is a tree iff it is connected
    const seen = new Array(n).fill(false);
    seen[0] = true;
    const queue = [0];
    for (let head = 0; head < queue.length; head++) {
        for (const next of graph[queue[head]]) {
            if (!seen[next]) {
                seen[next] = true;
                queue.push(next);
            }
        }
    }
    return queue.length === n; // every node was enqueued exactly once
};

C#:

using System.Collections.Generic;

public class Solution {
    public bool ValidTree(int n, int[][] edges) {
        // a tree on n nodes has exactly n - 1 edges
        if (edges.Length != n - 1) return false;

        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        foreach (var e in edges) {
            graph[e[0]].Add(e[1]);
            graph[e[1]].Add(e[0]);
        }

        // with n - 1 edges, the graph is a tree iff it is connected
        var seen = new bool[n];
        var queue = new Queue<int>();
        seen[0] = true;
        queue.Enqueue(0);
        int visited = 1;
        while (queue.Count > 0) {
            int node = queue.Dequeue();
            foreach (int next in graph[node]) {
                if (!seen[next]) {
                    seen[next] = true;
                    visited++;
                    queue.Enqueue(next);
                }
            }
        }
        return visited == n;
    }
}

C++:

#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        // a tree on n nodes has exactly n - 1 edges
        if ((int)edges.size() != n - 1) return false;

        vector<vector<int>> graph(n);
        for (const auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        // with n - 1 edges, the graph is a tree iff it is connected
        vector<bool> seen(n, false);
        queue<int> q;
        seen[0] = true;
        q.push(0);
        int visited = 1;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int next : graph[node]) {
                if (!seen[next]) {
                    seen[next] = true;
                    visited++;
                    q.push(next);
                }
            }
        }
        return visited == n;
    }
};

Complexity Analysis

  • Time: O(n + e) where e is the number of edges. After the first check e = n - 1, so this is O(n).
  • Space: O(n + e) for the adjacency list, visited array and queue, which is O(n) after the check.

Approach 2: Union-Find (Optimal)

Algorithm

Union-Find (disjoint set union) tracks which nodes are already connected without building an adjacency list. Process edges one by one: if an edge joins two nodes that are already in the same set, it closes a cycle. If every edge merges two different sets and there are exactly n - 1 edges, the n starting sets end up as one set, which is a tree.

  1. If len(edges) != n - 1, return false.
  2. Start with every node as its own set (parent[i] = i, size[i] = 1).
  3. For each edge (a, b), find the roots of a and b. If the roots are equal, return false (cycle).
  4. Otherwise merge the smaller set under the larger one.
  5. Return true: n - 1 merges with no cycle leave exactly one set.

find uses path halving (each node on the path is pointed at its grandparent) and unions go by size, which together give the near-constant amortized cost α(n), the inverse Ackermann function. find is a loop, not recursion, so deep chains cannot overflow the stack.

Implementation

Python:

from typing import List


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

        parent = list(range(n))
        size = [1] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path halving
                x = parent[x]
            return x

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:            # a and b already connected: cycle
                return False
            if size[ra] < size[rb]:  # union by size
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]

        # n - 1 successful merges leave exactly one component
        return True

Java:

class Solution {
    private int[] parent, size;

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

        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) return false;           // already connected: cycle
            if (size[ra] < size[rb]) {            // union by size
                int t = ra; ra = rb; rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
        }
        // n - 1 successful merges leave exactly one component
        return true;
    }

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

Go:

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 {
        return false
    }

    parent := make([]int, n)
    size := make([]int, n)
    for i := range parent {
        parent[i] = i
        size[i] = 1
    }
    find := func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]] // path halving
            x = parent[x]
        }
        return x
    }

    for _, e := range edges {
        ra, rb := find(e[0]), find(e[1])
        if ra == rb {
            return false // already connected: cycle
        }
        if size[ra] < size[rb] { // union by size
            ra, rb = rb, ra
        }
        parent[rb] = ra
        size[ra] += size[rb]
    }
    // n - 1 successful merges leave exactly one component
    return true
}

JavaScript:

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function (n, edges) {
    if (edges.length !== n - 1) return false;

    const parent = Array.from({ length: n }, (_, i) => i);
    const size = new Array(n).fill(1);
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    };

    for (const [a, b] of edges) {
        let ra = find(a), rb = find(b);
        if (ra === rb) return false;       // already connected: cycle
        if (size[ra] < size[rb]) [ra, rb] = [rb, ra]; // union by size
        parent[rb] = ra;
        size[ra] += size[rb];
    }
    // n - 1 successful merges leave exactly one component
    return true;
};

C#:

public class Solution {
    private int[] parent, size;

    public bool ValidTree(int n, int[][] edges) {
        if (edges.Length != n - 1) return false;

        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        foreach (var e in edges) {
            int ra = Find(e[0]), rb = Find(e[1]);
            if (ra == rb) return false;              // already connected: cycle
            if (size[ra] < size[rb]) (ra, rb) = (rb, ra); // union by size
            parent[rb] = ra;
            size[ra] += size[rb];
        }
        // n - 1 successful merges leave exactly one component
        return true;
    }

    private int Find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];           // path halving
            x = parent[x];
        }
        return x;
    }
}

C++:

#include <numeric>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if ((int)edges.size() != n - 1) return false;

        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);   // each node is its own set
        setSize.assign(n, 1);

        for (const auto& e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) return false;          // already connected: cycle
            if (setSize[ra] < setSize[rb]) swap(ra, rb); // union by size
            parent[rb] = ra;
            setSize[ra] += setSize[rb];
        }
        // n - 1 successful merges leave exactly one component
        return true;
    }

private:
    vector<int> parent, setSize;

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];       // path halving
            x = parent[x];
        }
        return x;
    }
};

Complexity Analysis

  • Time: O(n * α(n)). The edge-count check is O(1), then at most n - 1 edges are processed, each with two find calls that cost O(α(n)) amortized, plus O(n) to initialize the arrays.
  • Space: O(n) for the parent and size arrays. No adjacency list is built.

Key Insights

  • Tree = connected + acyclic = connected + (n - 1) edges: checking the edge count first turns the problem into a single connectivity check.
  • Union-Find detects cycles naturally: an edge whose endpoints already share a root closes a cycle.
  • Undirected graphs need no parent tracking with Union-Find: a DFS cycle check must ignore the edge back to its parent, which Union-Find sidesteps entirely.
  • Early exit: the edge-count check rejects most invalid inputs in O(1).

Edge Cases

  1. Single node, no edges (n = 1, edges = []): a lone node is a valid tree, so return true.
  2. Two nodes, no edges: disconnected, so false.
  3. Correct edge count but disconnected: for example n = 4, edges = [[0,1],[1,2],[2,0]] has 3 edges but a cycle among 0, 1, 2 and node 3 isolated. The count check passes, and the connectivity check (or the cycle check) catches it.
  4. Long chain (0-1-2-...-n-1): valid. Iterative traversal avoids deep recursion.
  5. Star shape: one center joined to all other nodes is valid.

Common Mistakes

  1. Only checking for cycles: an acyclic graph can still be a forest of several trees.
  2. Only checking connectivity: a connected graph can still have extra edges that create cycles (unless you also check the edge count).
  3. Treating the parent edge as a cycle in DFS: in an undirected graph each edge appears in both adjacency lists, so a naive DFS sees the edge back to its parent and reports a false cycle.
  4. Returning false for n = 1: zero edges is exactly n - 1 for a single node.
  5. Recursive find or recursive DFS on a long chain: without union by size, a chain of 2000 nodes can recurse deeply. Use iterative find and union by size.

Interview Tips

  1. State the definition you will check: “connected and acyclic, which for n nodes means connected with exactly n - 1 edges.”
  2. Offer both BFS/DFS and Union-Find. Union-Find is a nice fit because the input is already an edge list.
  3. Mention path compression (or halving) and union by size, and what α(n) means.
  4. Walk through a counterexample for each half of the definition: a cycle with an isolated node, and a forest.

Follow-up Questions

  1. Edges arrive one at a time: Union-Find handles streaming edges directly. Report “not a tree” the moment a cycle edge appears.
  2. Directed version: a rooted tree needs exactly one node with in-degree 0, every other node with in-degree 1, and all nodes reachable from the root.
  3. Which edge to remove to make a tree? That is Redundant Connection (LC 684): the first edge whose endpoints share a root.
  4. Count the trees in a forest: count components with Union-Find or BFS. See Number of Connected Components below.