Graph Valid Tree

The problem

You are given n, the number of nodes in a graph, numbered 0 to n - 1, and edges, a list of pairs. Each pair [a,b] is an edge that joins two different nodes a and b and can be walked in both directions. Return true if the graph is a tree and false if it is not. A graph is a tree when it is connected, meaning every node can be reached from every other, and has no cycle, where a cycle is a route that leaves a node and returns to it without using any edge twice. A single node with no edges is a tree.

What to write

function solve(n: number, edges: number[][]): boolean

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

Output
true

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

Output
false

Constraints

n ≥ 1; edges have distinct endpoints.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A tree must pass two tests, and a graph can fail either one alone. Every node can be reachable while the graph still holds a cycle. Or there can be no cycle at all while some node sits apart from the rest. With n = 1 and no edges the answer is true.

2. Hint 2: Ask a smaller question

   Draw 4 dots and join them into one connected piece using as few lines as you can. How many lines did you need? Now add one more line between any two dots. What has appeared in your drawing?

3. Hint 3: Name the pattern

   A connected graph on n nodes needs at least n - 1 edges, and with exactly that many it has none to spare for a cycle. So count the edges, then check that every node is reachable. That check is graph traversal with a visited set: walk from node 0, marking each node you meet so none is handled twice. Read the lesson on graph traversal with a visited set.

4. Hint 4: State the invariant

   Reached nodes whose neighbors are still unchecked wait their turn in a queue. Every node in the queue has been reached from node 0 and is already marked as seen, and no node joins the queue twice. So when the queue is empty, the seen set is exactly the set of nodes connected to node 0.

5. Hint 5: Sketch the pseudocode

   If the number of edges is not n - 1, return false. Build each node's list of neighbors, adding every edge at both ends. Mark node 0 as seen and put it in a queue. While the queue has nodes: take one, and mark and add each neighbor not yet seen. Return whether n nodes were seen.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

A connected undirected graph is a tree exactly when it has n-1 edges. Check the edge count and reachability.

The slow way

Check the two parts of the definition one by one: walk the graph looking for a cycle, then check that the walk reached every node. It works, but the cycle test is easy to get wrong. Every edge also leads back to the node you came from, and that must not count as a cycle. A walk that forgets this answers false on example 1.

The insight

Joining n nodes into one piece takes at least n - 1 edges: each new node needs one edge to attach it. An edge beyond those joins two nodes that are already connected, which closes a cycle. So a graph with exactly n - 1 edges is a tree exactly when it is connected, and that needs only one walk.

Step by step

1. Unless there are exactly n - 1 edges, the graph is not a tree. With fewer edges some node cannot be reached. With more, some edge must close a cycle. Either way the answer is false, and no walk is needed.
2. List the neighbors of every node, adding each edge in both directions. The walk needs to ask "where can I go from this node?" in one step. An edge can be walked both ways, so each end must appear in the other end's list.
3. Start at node 0: mark it as seen and put it in a queue. Any node of a connected graph reaches all the others, so node 0 will do. A queue is a line: nodes join at the back and leave from the front. The queue holds reached nodes whose neighbors are still unchecked.
4. Take the next node from the queue and look at each of its neighbors. Each neighbor is one step further along an edge. Looking at all of them means nothing reachable from this node can be missed.
5. A neighbor not seen before is marked and joins the queue. Marking a node when it joins the queue means it joins only once. Without the mark, two neighbors would keep adding each other and the loop would never end.
6. The graph is a tree exactly when the walk reached all n nodes. The walk reaches exactly the nodes connected to node 0. If that is all of them, the graph is connected, and with n - 1 edges a connected graph has no cycle.

The same numbered steps are the comments in each solution.

function solve(n, edges) {
  // 1. Unless there are exactly n - 1 edges, the graph is not a tree
  if (edges.length !== n - 1) return false;
  // 2. List the neighbors of every node, adding each edge in both directions
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  // 3. Start at node 0: mark it as seen and put it in a queue
  const seen = new Set([0]),
    q = [0];
  // 4. Take the next node from the queue and look at each of its neighbors
  // Removing the first item of an array is slow, so nothing is removed:
  // i is the position of the next node to take, and q.length grows as nodes join.
  for (let i = 0; i < q.length; i++)
    for (const next of adj[q[i]])
      // 5. A neighbor not seen before is marked and joins the queue
      if (!seen.has(next)) {
        seen.add(next);
        q.push(next);
      }
  // 6. The graph is a tree exactly when the walk reached all n nodes
  return seen.size === n;
}

function solve(n: number, edges: number[][]): boolean {
  // 1. Unless there are exactly n - 1 edges, the graph is not a tree
  if (edges.length !== n - 1) return false;
  // 2. List the neighbors of every node, adding each edge in both directions
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  // 3. Start at node 0: mark it as seen and put it in a queue
  const seen = new Set([0]),
    q = [0];
  // 4. Take the next node from the queue and look at each of its neighbors
  // Removing the first item of an array is slow, so nothing is removed:
  // i is the position of the next node to take, and q.length grows as nodes join.
  for (let i = 0; i < q.length; i++)
    for (const next of adj[q[i]])
      // 5. A neighbor not seen before is marked and joins the queue
      if (!seen.has(next)) {
        seen.add(next);
        q.push(next);
      }
  // 6. The graph is a tree exactly when the walk reached all n nodes
  return seen.size === n;
}

from collections import deque


def solve(n, edges):
    # 1. Unless there are exactly n - 1 edges, the graph is not a tree
    if len(edges) != n - 1:
        return False
    # 2. List the neighbors of every node, adding each edge in both directions
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    # 3. Start at node 0: mark it as seen and put it in a queue
    seen = {0}
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque([0])
    # 4. Take the next node from the queue and look at each of its neighbors
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            # 5. A neighbor not seen before is marked and joins the queue
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    # 6. The graph is a tree exactly when the walk reached all n nodes
    return len(seen) == n

Example 1, traced

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

Output
true

Why it works

A graph with fewer or more than n - 1 edges is never a tree, so the count check only rejects graphs that should be rejected. With exactly n - 1 edges, a tree is the same as a connected graph, and the walk marks exactly the nodes connected to node 0. Seeing all n nodes therefore means the graph is a tree.

Time and space

Time O(V + E), extra space O(V + E). V is the number of nodes (n), E of edges. Building the neighbor lists reads each edge once. The walk takes each node at most once and follows each edge at most twice. The lists hold 2E entries, and the seen set and the queue at most V nodes.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Reaching every node is not enough. Example 2 is connected, but its 5 edges are one more than n - 1 and contain a cycle. Without the edge count the answer comes out true instead of false.
• The edge count alone is not enough either. With n = 4, the three edges [0,1], [1,2], [2,0] pass the count, but they form a cycle and never reach node 3, so the answer is false.
• Add each edge to both ends' lists. With n = 2 and the one edge [1,0], lists built in one direction give node 0 no neighbors, so the walk stops and a real tree gets the answer false.

Pattern

Graph traversal with a visited set. Builds on Clone Graph and Course Schedule.

Keep going