Problem overview
The method validTree(n, edges) receives the number of nodes n, numbered 0 to n - 1, and an array edges where each entry [a, b] is an undirected edge. It returns true when the edges make the graph a tree, and false otherwise. A tree is connected, so you can get from any node to any other, and has no cycle. Equivalently, there is exactly one path between any two nodes.
For n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]] the answer is true: every node can be reached from node 0 and no edge closes a cycle. For edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] it is false, because the edges 1-2, 2-3 and 1-3 form a cycle. The third example, n = 4 with [[0, 1], [1, 2], [2, 0]], has 3 edges, the number a tree of 4 nodes has, but it is still false: the three edges form a cycle and node 3 has no edge at all.
The lesson asks for time close to O(n + e), where e is the number of edges, and O(n) extra space.
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 count the answer is false. With fewer edges some node is cut off, and with more some edge must close a cycle.
The count alone isn't enough, as the third example shows. But with exactly n - 1 edges, the graph is a tree exactly when no edge closes a cycle. The reason: if every edge joins two separate groups of nodes, each edge merges two groups into one, and n single nodes joined by n - 1 merges end up as one group, so the graph is connected.
Tracking groups is what union-find does. Each group is stored as a small tree in which 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 its two ends. If the roots are equal, the ends are already connected through other edges, so this edge would add a second path between them: a cycle. Otherwise, hang one root under the other.
Two refinements keep the trees shallow. Union by size always puts the smaller group under the larger one. Path halving makes each node visited during a search skip a level. Together they make each step cost O(α(n)) on average, where α is the inverse Ackermann function, which stays below 5 for any n a computer can hold.
Running the example n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]], the parent and size arrays after each edge are:
[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]All four edges merged two groups, and at the end every node leads to node 0. For the cycle in the third example, the edges [0, 1] and [1, 2] merge, and the edge [2, 0] finds the same root for both ends: node 0.
Step by step
- Check the edge count. If
edges.length !== n - 1, returnfalseright away. - Make every node its own group.
Array.from({length: n}, (_, i) => i)calls the arrow function once per index and keeps what it returns, soparent[i]isi. The first parameter is the unused value, named_. - Create
sizewithnones.size[r]is the number of nodes in the group whose root isr; only roots' entries are kept current. - Loop over the edges with
for...of. - Find the root of
edge[0]withthis.find(parent, edge[0])and keep it inrootA. It is declared withletbecause the swap below may change it. The helper is written afterwards. - Find the root of
edge[1]the same way, inrootB. - Detect the cycle. If
rootA === rootB, the ends are already connected, so returnfalse. - Union by size. If
size[rootA] < size[rootB], swap the two roots with[rootA, rootB] = [rootB, rootA], so thatrootAis the root of the larger group. A node moves one level deeper only when its group at least doubles, so no path gets longer than about log₂(n) steps. - Merge:
parent[rootB] = rootA. - Update the size:
size[rootA] += size[rootB]. The entry forrootBis never read again, because it isn't a root any more. - Return
trueafter the loop: no edge closed a cycle, and withn - 1edges that means one connected group. - Write
find(parent, x)as a second method of the class. - Walk up while
parent[x] !== x. A loop needs no call stack, however long the walk. - Halve the path:
parent[x] = parent[parent[x]]pointsxto its grandparent. - Move up:
x = parent[x], the grandparent it now points to. - Return
x, the root.
The solution in JavaScript
class Solution {
validTree(n, edges) {
if (edges.length !== n - 1) {
return false;
}
const parent = Array.from({length: n}, (_, i) => i);
const size = new Array(n).fill(1);
for (const edge of edges) {
let rootA = this.find(parent, edge[0]);
let rootB = this.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;
}
find(parent, x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
JavaScript details worth knowing:
Array.from({length: n}, fn)builds an array ofnelements from an object that only has alength. Each element is whatfn(value, index)returns. Withn = 3and(_, i) => iit gives[0, 1, 2], and with() => []it gives three separate empty arrays.- Destructuring swap.
[rootA, rootB] = [rootB, rootA]builds a temporary array of the two values and unpacks it in the other order. Withx = 1andy = 2,[x, y] = [y, x]leavesxas 2 andyas 1. Both variables must be declared withlet, which is whyrootAandrootBare notconst. - Arrays are passed by reference. When
findchangesparent,validTreesees the change. That is what makes path halving work. The parameterx, a number, is a copy, so changing it insidefinddoesn't affect the caller. - No recursion. The
whileloop infindnever grows the call stack. A recursive search down a chain of 100,000 nodes could run out of stack; the loop handles it, andvalidTree(100000, ...)on a path of 100,000 nodes returnstrue. !==and===compare numbers without any conversion, which is what the checks on counts and roots need.
Complexity
Time: O((n + e) · α(n)), nearly O(n + e). The edge count check is constant, creating the arrays is O(n), and each of the at most n - 1 edges costs two find calls. With union by size and path halving each costs O(α(n)) on average. Since the count check ensures e = n - 1, the total is nearly linear.
Space: O(n). The arrays parent and size have n entries each.
A BFS or DFS from node 0 that checks that every node is reached also runs in O(n + e) once the edge count is right. On a graph this size, use a BFS or a DFS with an explicit stack, because a recursive DFS down a long path can overflow the call stack.
Edge cases and common mistakes
- Trusting the count alone.
n = 4with[[0, 1], [1, 2], [2, 0]]has the right number of edges and is not a tree. The cycle check is what rejects it. - A single node.
n = 1with no edges returnstrue: 0 edges isn - 1, and the loop does nothing. - Isolated nodes.
n = 2with no edges returnsfalse, because 0 is notn - 1 = 1. Andn = 3with only[[0, 1]]returnsfalsefor the same reason. - Edge direction. The edges are undirected, so
[1, 0]connects the same nodes as[0, 1].n = 2with[[1, 0]]returnstrue. - Comparing nodes instead of roots. The cycle test compares
rootAwithrootB, notedge[0]withedge[1]. Two different nodes can share a root. - Linking the nodes instead of the roots. The merge must set
parent[rootB], notparent[edge[1]]. Linking a non-root node would leave its group's other nodes disconnected from the merge.
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,edges = []givestrue.n = 2,edges = []givesfalse.n = 4,edges = [[0, 1], [2, 3], [1, 2]]givestrue.
