LeetCode 261 - Graph Valid Tree

The problem asks whether a given undirected graph forms a valid tree. A tree is a special type of graph with two important properties: 1. The graph is fully connected, meaning every node can be reached from every other node. 2. The graph contains no cycles.

leetcodemediumdepth-first-searchbreadth-first-searchunion-findgraph-theory

LeetCode Problem 261

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

The problem asks whether a given undirected graph forms a valid tree.

A tree is a special type of graph with two important properties:

  1. The graph is fully connected, meaning every node can be reached from every other node.
  2. The graph contains no cycles.

The input consists of two parts:

  • n, the number of nodes in the graph, labeled from 0 to n - 1
  • edges, where each pair [a, b] represents an undirected connection between node a and node b

The goal is to return true if these edges form exactly one valid tree, otherwise return false.

For example, if every node is connected and there are no cycles, the graph is a tree. If there is a disconnected component or a cycle, the graph is not a tree.

The constraints are important because they guide the expected efficiency of the solution:

  • n can be as large as 2000
  • edges.length can be up to 5000

This means an exponential or repeated traversal solution would be too slow. We need a solution that runs approximately in linear time relative to the number of nodes and edges.

Several edge cases are especially important:

  • A graph with one node and no edges is a valid tree.
  • A graph with too many edges must contain a cycle.
  • A graph with too few edges cannot be fully connected.
  • Disconnected graphs are invalid even if they contain no cycles.
  • Cyclic graphs are invalid even if all nodes are reachable.

A key mathematical property of trees is extremely useful here:

A graph with n nodes is a valid tree if and only if:

  • it contains exactly n - 1 edges
  • it is fully connected

This observation simplifies the problem significantly.

Approaches

Brute Force Approach

A brute force solution would attempt to verify every tree property independently in a less optimized manner.

One possibility is:

  • For every node, perform a traversal to ensure all other nodes are reachable.
  • Separately check for cycles using repeated DFS or BFS traversals.
  • Recompute connectivity information multiple times.

This approach is correct because it explicitly validates the required tree properties. However, it performs unnecessary repeated work. Running graph traversals from many starting nodes leads to poor efficiency.

For example, if DFS is executed from every node, the complexity can approach O(n * (n + e)), which is unnecessarily expensive.

Optimal Approach

The optimal solution uses graph theory observations.

A valid tree must satisfy two conditions:

  1. The graph contains exactly n - 1 edges.
  2. The graph is connected.

Why does this work?

  • If a connected graph has exactly n - 1 edges, it cannot contain a cycle.
  • If a graph has fewer than n - 1 edges, it must be disconnected.
  • If a graph has more than n - 1 edges, it must contain a cycle.

Therefore, once we verify the edge count, we only need to confirm connectivity.

We can do this efficiently using DFS or BFS:

  • Build an adjacency list.
  • Start traversal from node 0.
  • Count how many nodes are visited.
  • If all nodes are visited and the edge count is n - 1, the graph is a valid tree.
Approach Time Complexity Space Complexity Notes
Brute Force O(n * (n + e)) O(n + e) Repeated graph traversals
Optimal O(n + e) O(n + e) Single traversal with edge-count property

Algorithm Walkthrough

  1. First, check whether the number of edges equals n - 1.

This is the most important early optimization. A valid tree with n nodes must contain exactly n - 1 edges. If this condition fails, we can immediately return false without performing any graph traversal. 2. Build an adjacency list representation of the graph.

Since the graph is undirected, every edge [a, b] is stored in both directions:

  • add b to a's neighbor list
  • add a to b's neighbor list

An adjacency list is chosen because it allows efficient traversal of sparse graphs and uses space proportional to the number of edges. 3. Create a set called visited.

This tracks which nodes have already been explored during DFS. Without this structure, the traversal could revisit nodes indefinitely in cyclic graphs. 4. Start DFS from node 0.

The traversal explores every reachable node from the starting point. 5. During DFS:

  • Mark the current node as visited.
  • Recursively visit all unvisited neighbors.

This gradually explores the entire connected component containing node 0. 6. After DFS completes, check how many nodes were visited.

If the graph is fully connected, every node should have been reached from node 0. 7. Return true only if all nodes were visited.

Combined with the earlier edge-count check, this guarantees the graph is a valid tree.

Why it works

The algorithm relies on a fundamental tree property:

An undirected graph is a tree if and only if:

  • it contains exactly n - 1 edges
  • it is connected

The edge-count condition eliminates all cyclic and under-connected cases. The DFS connectivity check ensures every node belongs to the same connected component. Together, these conditions are both necessary and sufficient.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # A valid tree with n nodes must have exactly n - 1 edges
        if len(edges) != n - 1:
            return False

        # Build adjacency list
        graph = defaultdict(list)

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()

        def dfs(node: int) -> None:
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        # Start DFS from node 0
        dfs(0)

        # Graph is a tree only if all nodes are connected
        return len(visited) == n

The implementation begins with the critical edge-count check. This immediately eliminates impossible cases and avoids unnecessary traversal work.

The adjacency list is constructed using defaultdict(list), which simplifies insertion logic and automatically initializes neighbor lists.

The visited set prevents revisiting nodes during DFS. This is essential for correctness and efficiency.

The nested dfs function recursively explores all reachable neighbors from the current node. Every visited node is added to the set exactly once.

After traversal finishes, the algorithm compares the number of visited nodes against n. If all nodes were reached, the graph is connected. Since the edge count was already validated, the graph must be a tree.

Go Solution

func validTree(n int, edges [][]int) bool {
    // A valid tree must have exactly n - 1 edges
    if len(edges) != n-1 {
        return false
    }

    // Build adjacency list
    graph := make([][]int, n)

    for _, edge := range edges {
        a := edge[0]
        b := edge[1]

        graph[a] = append(graph[a], b)
        graph[b] = append(graph[b], a)
    }

    visited := make([]bool, n)

    var dfs func(int)

    dfs = func(node int) {
        visited[node] = true

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    // Start DFS from node 0
    dfs(0)

    // Verify all nodes were visited
    for _, seen := range visited {
        if !seen {
            return false
        }
    }

    return true
}

The Go implementation follows the same overall algorithm as the Python version.

Instead of using a hash-based adjacency structure, Go uses a slice of slices: [][]int. Since node labels are guaranteed to be in the range [0, n - 1], direct indexing is efficient and straightforward.

The visited structure is implemented using a boolean slice instead of a set. This is more idiomatic and memory-efficient in Go.

Go does not support nested named functions in the same way as Python, so the DFS function is declared as a function variable and assigned recursively.

No special integer overflow handling is needed because the constraints are small.

Worked Examples

Example 1

Input:

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

First, verify the edge count:

len(edges) = 4
n - 1 = 4

The condition passes.

Build the adjacency list:

Node Neighbors
0 [1, 2, 3]
1 [0, 4]
2 [0]
3 [0]
4 [1]

DFS traversal:

Step Current Node Visited Set
1 0 {0}
2 1 {0,1}
3 4 {0,1,4}
4 2 {0,1,2,4}
5 3 {0,1,2,3,4}

All nodes were visited.

Result:

true

Example 2

Input:

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

Check edge count:

len(edges) = 5
n - 1 = 4

The condition fails immediately.

This graph must contain a cycle because it has too many edges for a tree.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n + e) Building the graph and DFS traversal each process nodes and edges once
Space O(n + e) Adjacency list and visited structures store graph information

The adjacency list stores every undirected edge twice, once for each direction, so its total size is proportional to e.

The DFS traversal visits every node once and examines every edge once, resulting in linear complexity relative to graph size.

The recursion stack can grow up to O(n) in the worst case for a chain-shaped graph.

Test Cases

from typing import List

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        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)

        visited = set()

        def dfs(node):
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        dfs(0)

        return len(visited) == n

solution = Solution()

assert solution.validTree(
    5,
    [[0,1],[0,2],[0,3],[1,4]]
) is True  # valid tree

assert solution.validTree(
    5,
    [[0,1],[1,2],[2,3],[1,3],[1,4]]
) is False  # contains cycle

assert solution.validTree(
    1,
    []
) is True  # single node tree

assert solution.validTree(
    2,
    []
) is False  # disconnected graph

assert solution.validTree(
    4,
    [[0,1],[2,3]]
) is False  # disconnected components

assert solution.validTree(
    4,
    [[0,1],[1,2],[2,3]]
) is True  # simple chain

assert solution.validTree(
    4,
    [[0,1],[1,2],[2,0]]
) is False  # cycle with disconnected node

assert solution.validTree(
    6,
    [[0,1],[0,2],[0,3],[3,4],[4,5]]
) is True  # larger valid tree

assert solution.validTree(
    6,
    [[0,1],[1,2],[2,3],[3,4],[4,5],[5,0]]
) is False  # large cycle
Test Why
n=5, valid connected graph Standard valid tree
Graph with extra edge Detects cycle
Single node with no edges Smallest valid tree
Two nodes with no edge Detects disconnected graph
Multiple disconnected components Ensures connectivity check works
Linear chain Valid sparse tree
Cycle plus isolated node Detects both cycle and disconnection
Larger connected structure Verifies general correctness
Large cycle Confirms cycle detection via edge count

Edge Cases

One important edge case is a graph with a single node and no edges. Many implementations accidentally reject this case because they assume at least one edge must exist. However, a single node is trivially connected and contains no cycles, so it is a valid tree. The implementation handles this correctly because len(edges) == n - 1 evaluates to 0 == 0, and DFS successfully visits the only node.

Another important case is a disconnected graph with too few edges. For example:

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

A naive implementation that only checks for cycles might incorrectly accept this graph because it has no cycle. However, trees must also be connected. The DFS traversal ensures this graph is rejected because only part of the graph becomes reachable from node 0.

A third important edge case is a graph containing a cycle. Cycles violate the tree property because there are multiple paths between nodes. Some implementations attempt expensive explicit cycle detection, but this solution handles the issue efficiently using the edge-count property. Any undirected connected graph with more than n - 1 edges must contain a cycle, so the algorithm immediately rejects such cases before traversal begins.