loading

Graph Valid Tree — Step-by-Step Visualization

mediumLeetCode #261GraphBreadth-First SearchDepth-First SearchUnion Find

You have a graph of `n` nodes labeled from `0` to `n - 1`. You are given an integer `n` and a list of `edges` where `edges[i] = [a_i, b_i]` indicates that there is an undirected edge between nodes `a_i` and `b_i` in the graph. Return `true` if the edges of the given graph make up a valid tree, and `false` otherwise. A tree is an undirected graph in which any two vertices are connected by exactly one path, which also implies it has no cycles.

Algorithm Pattern

Graph Properties (Cycle + Connectivity)

Key Idea

A graph is a valid tree if and only if it satisfies two conditions: 1. It is connected (all nodes are reachable from any node). 2. It has no cycles. For an undirected graph with `n` nodes to be a tree, it must also have exactly `n - 1` edges. We can use Union-Find or DFS to check for cycles and connectivity.

Step-by-Step Approach

  1. If `len(edges) != n - 1`, return `False` immediately.
  2. Build an adjacency list.
  3. Perform a DFS starting from node 0.
  4. Track visited nodes. If you revisit a node that isn't the direct parent, a cycle exists.
  5. After DFS, check if `len(visited) == n` (all nodes reached).

Common Gotchas

  • In an undirected graph, DFS needs to ignore the parent of the current node to avoid false cycle detection.
  • A tree with `n` nodes MUST have exactly `n-1` edges.

Related Problems

← All problems