Graph Valid Tree
Problem Statement
You are given n vertices labelled 0 to n - 1 and an undirected edge list edges, where each edge connects two vertices.
Return true if these edges form a valid tree, otherwise return false.
A valid tree must satisfy both properties: it is connected so every vertex can reach every other vertex, and it is acyclic so there is exactly one simple path between any pair of vertices.
Input
An integer n and an undirected edge list edges over vertices 0..n - 1.
Output
A boolean: true if the graph is one connected acyclic component, otherwise false.
Constraints
- •
1 <= n <= 2000 - •
0 <= edges.length <= 5000 - •
edges[i].length == 2 - •
0 <= ai, bi < n - •
ai != bi - •
There are no repeated edges.
Examples
Example 1
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
trueExample 2
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
falseExample 3
n = 4, edges = [[0,1],[2,3]]
falseLearning Objectives
- Recognise the tree invariant for undirected graphs: **n - 1 edges plus connectedness** is enough.
- Use Union-Find to detect whether an undirected edge closes a cycle while tracking component count.
- Use traversal with parent tracking to distinguish a real cycle from the harmless edge back to the parent.
- Learn when an edge-count precheck can simplify both correctness and runtime.
Intuition
A tree is the sparsest possible connected graph. With n vertices it uses exactly n - 1 edges: fewer edges cannot connect everything, and extra edges must create at least one cycle. That gives the fastest first filter: if edges.length != n - 1, the answer is immediately false.
After that, you only need one structural check. You can prove the graph is a tree by showing it is connected, or by showing no edge creates a cycle. Union-Find phrases the question as components: start with n separate sets and merge endpoints. If an edge tries to merge two vertices already in the same set, it found a cycle. Traversal phrases it as reachability: start from node 0, avoid walking directly back to the parent, and make sure every node is reached without seeing an already visited non-parent neighbor.
Senior interview framing: say the invariant first. The implementation is short because the invariant does the heavy lifting; you are not merely running DFS, you are proving connected plus acyclic with the minimum necessary checks.
Common mistakes
- ×Only checking **edges.length == n - 1**. That is necessary, but without connectivity or acyclicity reasoning it is not a complete proof in code interviews.
- ×Treating the parent edge in an undirected traversal as a cycle. When you move from 0 to 1, seeing 0 in 1's adjacency list is expected.
- ×Forgetting the edge-count short-circuit and doing extra work on obviously impossible inputs.
- ×Returning true after no Union-Find cycle but never verifying that all vertices ended in one component.
- ×Starting traversal at node 0 and returning true when the queue empties, without checking how many nodes were actually reached.
Algorithm Explanation
Union-Find path. First reject any graph whose edge count is not n - 1. Then create one set per vertex and process each edge. If the endpoints already share a root, the edge closes a cycle and the graph cannot be a tree. Otherwise merge the two components. At the end, require exactly one component.
Traversal path. The same edge-count precheck still applies. Build an undirected adjacency list, then BFS or DFS from vertex 0 while carrying the parent vertex for each state. A visited neighbor that is not the parent is a cycle. If traversal finishes without a cycle, the graph is a tree only when the reachable count equals n.
Union-Find is especially clean when edges are the natural input. Traversal is better when you already need adjacency lists, a reachable-node count, or a follow-up that asks for paths.
Solutions
Solution 1: Union-Find with component count
Prefer this when the input is an edge list and the interviewer cares about the tree invariant more than the actual traversal order. It short-circuits impossible edge counts, detects cycles online, and keeps connectivity as a component count.
A valid tree with n nodes must have n - 1 edges. After that precheck, every successful union reduces the component count by one. If an edge's endpoints already have the same root, adding it would create a cycle. The graph is valid only if all unions succeed and one component remains.
Step-by-step
- If edges.length != n - 1, return false immediately.
- Initialise parent and rank arrays with components = n.
- For each edge [u, v], call union. If u and v already share a root, return false because a cycle was found.
- Each successful union decrements the component count.
- Return whether components == 1.
O(E · α(V))
O(V)
The edge-count precheck is O(1); path compression and union by rank make each union nearly constant time.
Java implementation
Solution 2: BFS with parent tracking
Prefer this when you want to demonstrate the graph-traversal view, or when a follow-up may ask which nodes were reached or how to recover a path. It is also intuitive for candidates who have just practised connected-component BFS.
Build the undirected adjacency list and traverse from node 0. Carry the parent with every queued node so the edge back to the parent is ignored. Any other visited neighbor is a cycle; if no cycle appears, the final reachable count must still be n.
Step-by-step
- Reject immediately unless there are exactly n - 1 edges.
- Add every edge in both directions to an adjacency list.
- Start BFS from 0 with parent -1, mark on enqueue, and count nodes when dequeued.
- For each neighbor, skip only the parent. If a non-parent neighbor is already visited, return false.
- After the queue drains, return whether the traversal saw all n vertices.
O(V + E)
O(V + E)
The adjacency list stores two directed entries per undirected edge; visited and queue are O(V).
Java implementation
Dry Run
Sample input
Union-Find trace for n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]. The precheck passes because there are 4 = n - 1 edges.
| Step | Edge | Roots before | Action | Components |
|---|---|---|---|---|
| Start | - | 0, 1, 2, 3, 4 | Each node is its own set | 5 |
| 1 | [0,1] | 0 and 1 | Union them | 4 |
| 2 | [0,2] | 0 and 2 | Union them | 3 |
| 3 | [0,3] | 0 and 3 | Union them | 2 |
| 4 | [1,4] | 0 and 4 | Union them | 1 |
| End | - | One root | No cycle and all nodes connected | 1 |
Every edge merged two previously separate components, so no cycle appeared. The component count reached 1, therefore the graph is connected and acyclic: return true.
Interview Tips
Lead with the invariant: a tree on n nodes has exactly n - 1 edges and is connected. That sentence often earns more signal than jumping into code. Then choose the implementation based on the conversation: Union-Find is concise for edge lists and streaming edges; BFS or DFS is natural if the interviewer asks about reachability, parent tracking, or returning nodes in the component. If challenged on the final component check after the edge precheck, explain that it makes the proof explicit and protects the code if the precheck is later refactored away.
Likely follow-ups
- Return the edge that creates the cycle if the graph is not a tree.
- The graph is directed: what definition of tree or arborescence should be used?
- Edges arrive one at a time; report when the graph first stops being a valid tree.
- Count how many edges must be added to connect all components.
Similar Problems
Key Takeaways
- Tree validation is **connectivity + acyclicity**, not just a traversal template.
- The **n - 1** edge count is a powerful necessary condition and simplifies the rest of the proof.
- Union-Find detects undirected cycles when an edge connects two vertices already in the same set.
- In undirected BFS or DFS, ignore the parent edge but reject any other visited neighbor.