Graph Valid Tree

Difficulty: Medium

Problem

You have n nodes numbered 0 to n-1 and a list of undirected edges between them. Decide whether the edges form a valid TREE and return true if so, false otherwise. You spent a whole track climbing trees; now show you know what one is: everything in one connected piece, and not a single cycle.

Example

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[4,5]]
Output: true
Explanation: Five edges join all six nodes into one piece with no loop anywhere: that is a tree.

Brute-force approach

No brute-force phase for graph problems. The insight (edge count + one flood) IS the algorithm.

Optimal approach

Key insight: Edges are a budget: connecting n nodes costs exactly n−1, and a cycle overspends. Right count + full reach = tree, no explicit cycle detection needed.

Check the edge count (must be exactly n−1), then run one BFS from node 0 and verify it reaches all n nodes.

Steps

  1. If len(edges) ≠ n − 1, return false immediately
  2. Build the adjacency list (both directions)
  3. BFS from node 0 with a visited set
  4. Return whether visited grew to all n nodes

Time complexity: O(V + E) · Space complexity: O(V + E)

Pseudocode

function validTree(n, edges):
    if length(edges) != ____:
        return false
    
    adj = adjacency list from edges (both directions)
    visited = {____}
    queue = [0]
    
    while queue not empty:
        cur = queue.pop_front()
        for nb in adj[cur]:
            if nb not in visited:
                visited.add(____)
                queue.push(nb)
    
    return size(visited) == ____

Hints

  • The tree budget: how many edges must n nodes have, exactly?
  • The flood starts somewhere. Node 0 is as good as anywhere, and starts already visited
  • Standard BFS bookkeeping: mark the neighbor the moment you discover it
  • Full reach = tree: compare the visited count against what?

Complexity questions

What is the total time complexity?

O(V + E): one O(1) comparison plus one flood. Building adjacency is O(E), the BFS touches each node and edge once: O(V + E). And since a passing input has E = V − 1, this is effectively O(V).

What is the space complexity?

O(V + E): adjacency list, visited set, queue. The adjacency list stores each edge twice (O(E)), and visited plus the queue hold at most V entries.

Why does 'exactly n−1 edges AND connected' guarantee NO cycles, without checking for them?

A cycle would waste an edge joining already-connected nodes, leaving fewer than n−1 for attachments. Some node would be unreachable, contradicting connectivity. Connecting n nodes requires n−1 productive edges minimum. If one of our n−1 edges sits in a cycle, it was unproductive: the remaining n−2 can't connect n nodes. Connected + n−1 edges therefore forces every edge to be productive: acyclic.

Another classic solution processes edges one by one, asking 'are these two endpoints ALREADY connected?'. What structure answers that query near-instantly?

Union-Find (disjoint set union). If the endpoints already share a set, this edge closes a cycle. Union-Find merges sets as edges arrive; an edge whose endpoints are already in the same set is exactly a cycle-closer. It's the other standard answer to this problem, and worth learning when you meet Kruskal's algorithm.

Check your understanding of Graph Valid Tree

What TWO properties make a graph a valid tree?

Connected (one piece) AND acyclic (no loops). A tree is exactly a connected, acyclic graph. Roots and leaves are just roles we assign afterwards. Any node of a valid tree can play root.

How many edges must a tree with n nodes have?

n − 1, exactly. Exactly n − 1. Every node except a 'first' one needs exactly one edge to join the structure. Fewer edges → someone is disconnected. More → some edge closes a loop.

The graph has exactly n − 1 edges. What single check finishes the job?

Check connectivity: one BFS/DFS from node 0 must reach all n nodes. With exactly n − 1 edges, connected and acyclic imply each other. If a cycle existed, it would 'waste' an edge and leave some node unreachable. So one flood from node 0 settles everything.

n = 4, edges = [[0,1],[2,3]]. Valid tree?

No: only 2 edges (needs 3), and it's split into two pieces. It's acyclic, but it's a FOREST: two separate pieces and only 2 edges where a 4-node tree needs 3. Both the edge count and the connectivity check reject it.

Why is the edge-count check done FIRST?

It's O(1): one comparison eliminates every wrong-count input before any traversal runs. len(edges) != n − 1 is a single comparison that instantly rejects half of all invalid inputs. Cheapest checks first is a habit worth keeping.

Related problems

Keep practising