Problem overview
The function validTree gets n, the number of nodes (numbered 0 to n - 1), and a slice edges of pairs. Each pair [a, b] is an undirected edge between two nodes. The function returns true when the edges make the graph a tree, and false otherwise.
A graph is a tree when it is connected, meaning you can get from any node to any other, and has no cycle. Equivalently, there is exactly one path between any two nodes.
With n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], every node is reachable from node 0 and no edge closes a cycle, so the answer is true. With n = 5 and [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] the edges 1-2, 2-3 and 1-3 form a cycle, so the answer is false. With n = 4 and [[0, 1], [1, 2], [2, 0]] the answer is also false: there are 3 edges, the right count for 4 nodes, but they form a cycle and node 3 has no edge at all.
The lesson asks for O((n + e) · α(n)) time, nearly O(n + e), and O(n) extra space, where e is the number of edges and α is the inverse Ackermann function, which stays below 5 for any n a computer can hold.
Approach: count the edges, then look for a cycle
A tree with n nodes has exactly n - 1 edges. That gives a quick first test: with any other number of edges the answer is false. With fewer, some node is cut off from the rest. With more, some edge must close a cycle.
The count alone is not enough, as the third example shows. But once there are exactly n - 1 edges, the graph is a tree exactly when no edge closes a cycle. If every edge joins two separate groups of nodes, each edge merges two groups into one, and the n single nodes we started with end up as one group after n - 1 merges.
Union-find tracks those groups. Each group is stored as a tree of parent pointers, and its root, the one node that is its own parent, names the group. For each edge, find the root of each end. If the roots are equal, the ends are already connected, so this edge would be a second path between them: a cycle. Otherwise merge the two groups.
A DFS or BFS from node 0 that checks every node is reached also works in O(n + e) once the count is right. On a graph with 100,000 nodes, use a BFS or a DFS with its own stack, since a recursive DFS down a long path can run out of call stack. This lesson uses union-find.
Step by step
- Check the edge count. If
len(edges) != n - 1, returnfalse. - Create
parentwithmake([]int, n).parent[x]will hold the parent of nodex. - Create
sizethe same way.size[r]counts the nodes in the group whose root isr. Only the roots' entries are kept up to date. - Loop over the nodes to start each one in a group of its own.
- Set
parent[i] = i. A node that is its own parent is a root. - Set
size[i] = 1.makefilled the sizes with zeros, so they must be set. - Loop over
edgeswithfor _, edge := range edges. - Find the root of
edge[0]with the helperfind, intorootA. The helper is written afterwards. - Find the root of
edge[1]intorootB. - Test
rootA == rootB. If so, returnfalse: the ends are already connected, so this edge closes a cycle. - Union by size. If
size[rootA] < size[rootB], swap the two roots so thatrootAis the root of the larger group. Go evaluates the whole right side before assigning, sorootA, rootB = rootB, rootAswaps them. - Merge:
parent[rootB] = rootAhangs the smaller tree under the larger one's root. - Update the size:
size[rootA] += size[rootB]. The entrysize[rootB]is never read again, becauserootBis no longer a root. - Return
trueafter the loop: no edge closed a cycle, so alln - 1edges merged groups, and the graph is connected. - Write
findwith parametersparent []intandx int, returning the root ofx's group. - Loop while
parent[x] != x, that is, whilexis not a root. A loop uses no call stack, however long the walk is. - Path halving: set
parent[x] = parent[parent[x]], so the node points to its grandparent. - Move up:
x = parent[x]. Since the parent is now the old grandparent, each turn climbs two levels. - Return
x, the root.
The solution in Go
func validTree(n int, edges [][]int) bool {
if len(edges) != n - 1 {
return false
}
parent := make([]int, n)
size := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
size[i] = 1
}
for _, edge := range edges {
rootA := find(parent, edge[0])
rootB := find(parent, edge[1])
if rootA == rootB {
return false
}
if size[rootA] < size[rootB] {
rootA, rootB = rootB, rootA
}
parent[rootB] = rootA
size[rootA] += size[rootB]
}
return true
}
func find(parent []int, x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
The Go details worth a closer look:
- Slices share their array.
findreceivesparentas a slice, which is a small header pointing at the same array. Whenfindwritesparent[x] = parent[parent[x]],validTreesees the change. - Other parameters are copies. Changing
xinsidefindchanges only its own copy of the number. - Tuple assignment.
rootA, rootB = rootB, rootAneeds no temporary variable. forwith only a condition.for parent[x] != xis Go'swhile. Go has no other loop keyword.
Complexity
Time: O((n + e) · α(n)). Setting up the table is O(n). Then each of the at most n - 1 edges (after the count check) costs two find calls and a constant amount of other work. With union by size no root path gets longer than log₂(n) steps, and with path halving a call costs O(α(n)) on average, nearly constant.
Space: O(n). The slices parent and size hold one number per node.
Edge cases and common mistakes
- Trusting the count. With 3 edges for 4 nodes,
[[0, 1], [1, 2], [2, 0]]passes the count test but fails the union-find: the edge[2, 0]finds the same root for both ends. - A single node.
validTree(1, [][]int{})returnstrue: zero edges isn - 1, and the loop never runs. - Two nodes, no edge.
validTree(2, [][]int{})returnsfalseat the count check, since 0 is not 1. - Disconnected pieces with the wrong count.
[[0, 1], [2, 3]]for 4 nodes has 2 edges, not 3, so it fails the count. - Comparing nodes instead of roots. Two nodes are in the same group exactly when
findreturns the same root, not when theirparentvalues are equal. - Edge direction. Edges are undirected, so
[1, 0]and[0, 1]mean the same thing.
Testing
Here is the state after each edge of the first example (n = 5), printed as the parent and size slices:
[0 1] parent [0 0 2 3 4] size [2 1 1 1 1]
[0 2] parent [0 0 0 3 4] size [3 1 1 1 1]
[0 3] parent [0 0 0 0 4] size [4 1 1 1 1]
[1 4] parent [0 0 0 0 0] size [5 1 1 1 1]
no cycleAll five nodes end up under root 0, so the function returns true. For n = 4 with the edges [[0, 1], [1, 2], [2, 0]], the count check passes and the third edge stops the run:
[0 1] parent [0 0 2 3] size [2 1 1 1]
[1 2] parent [0 0 0 3] size [3 1 1 1]
[2 0] same root 0 -> cycleMore inputs to try:
n = 5,[[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]givesfalse.n = 1, no edges, givestrue.n = 2, no edges, givesfalse.n = 2,[[1, 0]]givestrue.n = 4,[[0, 1], [2, 3]]givesfalse.
