Problem overview
The method validTree(n: Int, edges: Array[Array[Int]]): Boolean gets a graph of n nodes, numbered from 0 to n - 1, and a list of undirected edges. It returns true when the graph is a tree: connected, so every node can reach every other, and free of cycles. Put another way, there is exactly one path between any two nodes.
With n = 5 and edges [0, 1], [0, 2], [0, 3], [1, 4] the answer is true: every node hangs off node 0 and no edge closes a loop. With edges [0, 1], [1, 2], [2, 3], [1, 3], [1, 4] the answer is false, because the edges 1-2, 2-3 and 1-3 form a cycle.
The third example is a warning: n = 4 with edges [0, 1], [1, 2], [2, 0] has three edges, the number a tree of 4 nodes needs, and still the answer is false. The edges form a cycle and node 3 has no edge at all. Counting edges is necessary but not sufficient.
Approach: count the edges, then look for a cycle
A tree with n nodes has exactly n - 1 edges. With fewer, some node is cut off from the rest. With more, some edge closes a cycle. So the first test is the count: any other number of edges returns false at once.
With exactly n - 1 edges, the graph is a tree exactly when no edge closes a cycle. If every one of the n - 1 edges joins two separate groups, the n single nodes we start with end up as one group, so the graph is connected as well.
That suggests union-find. It keeps each group of connected nodes as a small tree of its own: every node points to a parent, and the root, the one node that is its own parent, names the group. To process an edge, find the roots of both ends. If the roots are equal, the ends are already connected through other edges, and this edge would add a second path between them: a cycle. If the roots differ, merge the groups by hanging one root under the other.
Two refinements keep the trees shallow. Union by size always hangs the smaller group under the larger one. Path halving makes each node visited during a search skip one level. Together they make each step cost O(α(n)), where α is the inverse Ackermann function, below 5 for any size a computer can hold.
Here is the state after each edge for the first example, n = 5, as parent and size arrays:
start parent=[0,1,2,3,4] size=[1,1,1,1,1]
edge 0-1: parent=[0,0,2,3,4] size=[2,1,1,1,1]
edge 0-2: parent=[0,0,0,3,4] size=[3,1,1,1,1]
edge 0-3: parent=[0,0,0,0,4] size=[4,1,1,1,1]
edge 1-4: parent=[0,0,0,0,0] size=[5,1,1,1,1]
The second example reaches the edge 1-3 after three merges, when nodes 1 and 3 already lead to root 0:
start parent=[0,1,2,3,4] size=[1,1,1,1,1]
edge 0-1: parent=[0,0,2,3,4] size=[2,1,1,1,1]
edge 1-2: parent=[0,0,0,3,4] size=[3,1,1,1,1]
edge 2-3: parent=[0,0,0,0,4] size=[4,1,1,1,1]
edge 1-3: roots both 0 -> cycle
Step by step
- Check the edge count. If
edges.length != n - 1, returnfalse. - Create
parentwithArray.tabulate(n)(i => i). Elementiisi, so every node starts as the root of a group of one. - Create
sizewithArray.fill(n)(1).size(r)counts the nodes in the group whose root isr; only roots' entries are kept up to date. - Loop over the edges with
edge <- edges. - Find the root of
edge(0)and keep it inrootA, avar, because the size step may swap it. The helperfindis written at the end. - Find the root of
edge(1)the same way, inrootB. - If
rootA == rootB, returnfalse. Both ends already lead to the same root, so this edge adds a second path between them. - Test
size(rootA) < size(rootB). If the group ofrootAis the smaller one, swap the roots so thatrootAis always the root of the larger group. - Swap through a temporary: save
rootAintemp, copyrootBintorootA, then puttempintorootB. - Merge:
parent(rootB) = rootAhangs the smaller tree under the larger one's root. - Update the size:
size(rootA) += size(rootB). The size ofrootBis never read again, because it is no longer a root. - Return
trueafter the loop: no edge closed a cycle. - Write
find(parent: Array[Int], node: Int): Int. It copiesnodeinto avar x, because a parameter cannot be reassigned. - Loop while
parent(x) != x, that is, whilexis not a root. Setparent(x)toparent(parent(x))(path halving), then setxtoparent(x). - Return
x, the root.
The solution in Scala
class Solution {
def validTree(n: Int, edges: Array[Array[Int]]): Boolean = {
if (edges.length != n - 1) {
return false
}
val parent = Array.tabulate(n)(i => i)
val size = Array.fill(n)(1)
for (edge <- edges) {
var rootA = find(parent, edge(0))
var rootB = find(parent, edge(1))
if (rootA == rootB) {
return false
}
if (size(rootA) < size(rootB)) {
val temp = rootA
rootA = rootB
rootB = temp
}
parent(rootB) = rootA
size(rootA) += size(rootB)
}
true
}
def find(parent: Array[Int], node: Int): Int = {
var x = node
while (parent(x) != x) {
parent(x) = parent(parent(x))
x = parent(x)
}
x
}
}
The Scala details worth a closer look:
Array.tabulate(n)(i => i)builds an array ofnelements where elementiis the function's result fori. Here the function just returns its argument.Array.fill(n)(1)gives every element the same value instead.- Arrays are shared, not copied.
findreceives the array itself, so when it changesparentthrough path halving,validTreesees the change. That is whyfindcan write to the array and return only the root. size(rootA) += size(rootB)is shorthand forsize(rootA) = size(rootA) + size(rootB)on an array element.varfor the roots.rootAandrootBget new values in the swap, so they arevars.tempnever changes, so it is aval.returninsidefor. The last expression of a Scala method is its value, sotrueandxneed noreturn. Early exits do. The firstreturn falsesits outside the loop. The second one, inside theforbody, is a non-local return, because the body of aforis a function. Scala 3.5 compiles it, and it works, but the compiler warns that non-local returns are no longer supported.- The loop in
findavoids recursion. A chain of 100,000 nodes would be a problem for a recursive version;whileneeds no extra stack. A path of 100,000 nodes, with edges[0, 1], [1, 2]and so on, returnstrue.
Complexity
Let e be the number of edges. After the count check, e = n - 1.
Time: O((n + e) · α(n)), nearly O(n + e). Creating the arrays costs O(n), and each edge costs two find calls and a merge, each close to constant time thanks to union by size and path halving.
Space: O(n). The two arrays hold one entry per node.
A DFS or BFS from node 0 that checks every node was reached also works once the edge count is right. On a graph this size it needs its own stack or queue rather than recursion.
Edge cases and common mistakes
- One node, no edges.
n = 1with no edges is a tree: the count0equalsn - 1, the loop does nothing and the method returnstrue. - Two nodes, no edges.
n = 2with no edges givesfalse: the count is 0 instead of 1. - Disconnected graphs.
n = 4with edges[0, 1], [2, 3]givesfalsefrom the count alone: 2 edges, and a tree of 4 nodes has 3. With the right count, a disconnected graph must contain a cycle, which the root comparison finds, as in the third example. - Edge direction. The graph is undirected, so
[1, 0]means the same as[0, 1]:n = 2with[1, 0]givestrue. - Counting edges only. The third example shows why: the right number of edges does not make a tree.
- Comparing parents instead of roots. Two nodes can have different parents and still lie in the same group. Compare roots, found with
find. - Merging without finding roots. Setting
parent(edge(1)) = edge(0)directly would detach part of an existing group.
Testing
n = 5, edges[0, 1], [0, 2], [0, 3], [1, 4]givestrue.n = 5, edges[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]givesfalse.n = 4, edges[0, 1], [1, 2], [2, 0]givesfalse.n = 1, no edges, givestrue.n = 2, no edges, givesfalse.n = 2, edges[1, 0], givestrue.n = 4, edges[0, 1], [2, 3]givesfalse.n = 4, edges[0, 1], [1, 2], [2, 3]givestrue.
