Graph Valid Tree

The problem

You are given node_count nodes, numbered 0 to node_count - 1, and a list of undirected edges. Each edge [first, second] joins nodes first and second. Return true if these edges form a valid tree, and false if not.

A tree is a graph where every node can reach every other node, and there are no loops.

Example 1

Input: node_count = 5, edges = [[0, 1], [0, 2], [2, 3], [2, 4]]

Output: true

Every node hangs off node 0, directly or through node 2, and there is no loop.

Example 2

Input: node_count = 5, edges = [[0, 1], [1, 2], [2, 0], [3, 4]]

Output: false

The edge count is right, but 0, 1 and 2 form a loop, and 3 and 4 are cut off from them.

Example 3

Input: node_count = 4, edges = [[0, 1], [2, 3]]

Output: false

Only 2 edges for 4 nodes, so the graph falls apart into two pieces.

Constraints

• 1 ≤ node_count ≤ 2000 (call it n)
• 0 ≤ edges.length ≤ 5000 (call it E)
• No edge joins a node to itself, and no edge appears twice.

Clarifying questions

Are the edges directed?

No. [0, 1] lets you go from 0 to 1 and from 1 to 0.

Can the same edge appear twice?

No. Every edge is different, and none joins a node to itself.

Is a single node with no edges a tree?

Yes. One node is connected and has no loop.

Does it matter which node is the root?

No. Any node can be the root of a tree, so we only check the shape.

Spot the pattern

A tree has two properties: it is connected, and it has no cycle. “Is everything connected?” is a reachability question, so it is graph search. And there is a counting fact that saves us from looking for cycles: a connected graph on n nodes with exactly n − 1 edges cannot have a loop.

Solutions

Count, then searchO(n)

Show all

There is only one approach worth showing. Every edge must be read at least once, and this reads each one a fixed number of times. Union-find is the other common answer and costs about the same.

Count, then search O(n)

The idea

Use two facts about trees on n nodes.

1. A tree has exactly n − 1 edges. With fewer, some node is cut off. With more, some edge closes a loop. So if the count is wrong, return false at once.
2. With exactly n − 1 edges, the graph is a tree exactly when it is connected.

To check connected, build each node’s list of neighbors, then run one search from node 0. Mark each node the first time it is seen. If the search marks all n nodes, return true.

Why it is correct: a connected graph always contains a tree that uses n − 1 of its edges. If the graph has only n − 1 edges, it is that tree, with nothing left over to make a loop.

Walkthrough

stack top →

empty

seen

0

1. if len(edges) != node_count - 1: return False
2. neighbors = neighbor lists built from edges
3. seen = {0}; stack = [0]
4. while stack:
5. node = stack.pop()
6. for neighbor in neighbors[node]:
7. if neighbor not in seen: seen.add(neighbor); stack.push(neighbor)
8. return len(seen) == node_count

A tree on 5 nodes needs exactly 4 edges. Fewer cannot join every node, and more must close a loop. Here there are 4, so the count is right.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Count, then search: a tree on n nodes has exactly n - 1 edges and is
    // connected. One search from node 0 checks the second part in O(n) time.
    public boolean validTree(int nodeCount, int[][] edges) {
        // Fewer edges cannot connect n nodes; more edges must close a loop.
        if (edges.length != nodeCount - 1) return false;
        List<List<Integer>> neighbors = new ArrayList<>();
        for (int i = 0; i < nodeCount; i++) neighbors.add(new ArrayList<>());
        for (int[] edge : edges) {
            neighbors.get(edge[0]).add(edge[1]);
            neighbors.get(edge[1]).add(edge[0]);
        }
        boolean[] seen = new boolean[nodeCount];
        Deque<Integer> stack = new ArrayDeque<>();
        seen[0] = true;
        stack.push(0);
        int count = 1;
        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int neighbor : neighbors.get(node)) {
                if (!seen[neighbor]) {
                    seen[neighbor] = true;
                    count++;
                    stack.push(neighbor);
                }
            }
        }
        // With n - 1 edges, reaching every node also rules out a cycle.
        return count == nodeCount;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are three loops. Building the lists reads each edge once. The while loop pops one node per run. The inner for looks at each neighbor of that node. Each of these is a fixed job, so 1 step.

   1. if len(edges) != node_count - 1: return False
   2. neighbors = neighbor lists built from edges
   3. seen = {0}; stack = [0]
   4. while stack:
   5. node = stack.pop()
   6. for neighbor in neighbors[node]:
   7. if neighbor not in seen: seen.add(neighbor); stack.push(neighbor)
   8. return len(seen) == node_count

2. 2 Count the runs on Example 1

   The table has one column per node, in the order they were popped. Every node is popped once, and looks at all its neighbors. Node 2 has the most: 0, 3 and 4.

   4 edges read + 5 pops + 8 neighbor looks = 17 steps.

   popped	node 0	node 2	node 4	node 3	node 1
   pops	1	1	1	1	1
   neighbors looked at	2	3	1	1	1

   total

   4 edges read + 5 pops + 8 looks = 17

3. 3 Write the count for any n

   A node is pushed only the first time it is seen, so it is popped at most once. Each edge appears in two neighbor lists, so the looks add up to 2 × E:

   E + n + 2 × E = n + 3 × E steps

   The first line already returned unless E = n − 1, so this is n + 3 × (n − 1) = 4 × n − 3 steps.

   Check it with Example 1: 4 × 5 − 3 = 17. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the 4 and the 3. What is left is n. The early return is what makes this O(n) rather than O(n + E): a long edge list is rejected before it is even read.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The neighbor lists hold 2 × (n − 1) entries. The seen set and the stack hold at most n nodes each. So the space is O(n).

   neighbor lists (2 × E entries)seen (n)stack (up to n)

Common mistake

Checking only that every node is reached

Reaching every node proves the graph is connected, but not that it has no loop. Example 2 with one more edge, 2–3, reaches all 5 nodes and still has a loop. The edge count check is what rules loops out.

Tested at the limits

2,000 random graphs of up to 6 nodes. Half have exactly n − 1 edges, the hard case: either a tree, or a loop that leaves a node cut off. Count, then search gave the same answer every time as a simple union-find check written in the test.

Largest inputs	Result
A line through all 2,000 nodes (the most allowed), in random order, so the search walks the whole line. Count, then search.	Under 0.01 s, and about 0.3 MB of extra memory: the neighbor lists and the seen set, O(n).
2,000 nodes and 5,000 edges (the most edges allowed). Count, then search.	Under 0.01 s, and almost no memory: 5,000 is not n − 1 = 1,999, so the count says no before any search.