Problem overview
The method validTree receives n, the number of nodes (numbered 0 to n - 1), and edges, an array of [a, b] pairs that each join two nodes. It returns true when the graph is a tree and false otherwise. A tree is connected (you can get from any node to any other) and has no cycle, which is the same as saying there is exactly one path between any two nodes.
For n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]] every node hangs off node 0 or node 1 and no edge closes a loop, so the answer is true. For 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. The third example, n = 4 with [[0, 1], [1, 2], [2, 0]], has the 3 edges a 4-node tree needs, but they form a cycle and node 3 is isolated, so the answer is false: counting edges is not enough.
The statement asks for nearly linear time, O((n + e) · α(n)), where e is the number of edges and α is the inverse Ackermann function, 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 fewer edges some node is cut off, and with more, some edge must close a cycle. Either way the answer is false.
With exactly n - 1 edges, the graph is a tree exactly when no edge closes a cycle. Why: if no edge closes a cycle, every edge joins two separate groups of nodes, so each edge reduces the number of groups by one, and the n single nodes become one group after n - 1 edges. The graph is then connected and has no cycle.
To detect a cycle, use union-find. It keeps each group of connected nodes as a small tree in an array: parent[i] is the node above i, and the root, the one node that is its own parent, names the group. To process an edge:
- Find the root of each end.
- If the roots are equal, the two ends are already connected through other edges, so this edge adds a second path between them: a cycle.
- Otherwise merge the groups by hanging one root under the other.
Two refinements keep the trees shallow. Union by size hangs the smaller group under the larger, and path halving makes nodes skip a level each time find walks past them. Together they make each operation almost constant time.
A DFS or BFS from node 0 that checks every node was reached also works once the count is right. On a graph with 100,000 nodes, use a BFS or a DFS with its own stack, because a recursive DFS along a long path can run out of call stack.
Tracing the examples
In the first example, the edges merge the groups one at a time. The 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 five nodes end up under root 0, and the function returns true. The second example is rejected by the count: it has 5 edges for 5 nodes, so the first test returns false before any union-find work happens. In the third example the count is right, so the loop runs:
[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
The third edge joins node 2 and node 0, which already share root 0, so the function returns false.
Step by step
- Check the edge count. If
edges.length !== n - 1, returnfalse. - Create
parentwithArray.from({length: n}, (_, i) => i). The arrow function runs once per index and returns the index, so every node starts as its own root. The first parameter, named_, is the unused value. - Create
sizewithnones.size[r]counts the nodes of the group whose root isr; only the roots' entries are kept up to date. - Loop over
edgeswithfor...of. Each edge either merges two groups or closes a cycle. - Find the root of
edge[0]intorootA, declared withletbecause the swap below may change it. The helperfindis written at the end. - Find the root of
edge[1]intorootB. - If the roots are equal, return
false. The ends are already connected, and this edge would add a second path. - Make
rootAthe larger group's root: ifsize[rootA] < size[rootB], swap them with[rootA, rootB] = [rootB, rootA]. A node then moves one level deeper only when its group at least doubles, so no walk to a root gets longer than about log2(n) steps. - Merge: set
parent[rootB]torootA. - Update the size:
size[rootA] += size[rootB]. The size ofrootBis never read again, since it isn't a root any more. - Return
trueafter the loop. Every one of then - 1edges merged two groups, so the graph is connected and has no cycle. - Write
findas a method of the class, takingparentand a nodexand returning the root. - Loop while
parent[x] !== x. The root is the only node that is its own parent. A loop needs no call stack, however long the walk is. - Point
xto its grandparent:parent[x] = parent[parent[x]]. This is path halving: each node passed skips one level, so later walks from there are shorter. - Move up:
x = parent[x], which is now the old grandparent. - Return
x, the root.
The solution in TypeScript
class Solution {
validTree(n: number, edges: number[][]): boolean {
if (edges.length !== n - 1) {
return false;
}
const parent: number[] = Array.from({length: n}, (_, i) => i);
const size: number[] = 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: number[], x: number): number {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
Some TypeScript details:
Array.from({length: n}, fn)treats the object as an array-like of lengthnand callsfn(value, index)for each position. It returns a new array, soArray.from({length: 3}, (_, i) => i)is[0, 1, 2].- Swapping with destructuring.
[rootA, rootB] = [rootB, rootA]builds a temporary array of the two values, then assigns its elements back in the other order. No third variable is needed. Both variables must be declared withlet, which is whyrootAandrootBare. - Arrays are shared.
findreceives the same array object asvalidTree, not a copy, so the changes it makes toparentare visible to the caller. That is how path halving speeds up later calls. constarrays can change.parentandsizeareconst, which only means the names can't be reassigned. Their elements can.- Types are erased.
number[]andnumber[][]only help the compiler; the compiled JavaScript has no types.
Complexity
Time: nearly O(n + e). The edge count is checked in constant time. Building the arrays is O(n). Each of the at most n - 1 edges costs two find calls and a merge, each close to constant time with union by size and path halving; the cost per operation is O(α(n)) on average, and α(n) is below 5 for any n a computer can hold.
Space: O(n). The arrays parent and size hold one number per node.
Edge cases and common mistakes
- A single node.
n = 1with no edges returnstrue: 0 edges equalsn - 1, and the loop doesn't run. - Two nodes, no edge.
n = 2with[]returnsfalse, because the count is 0 instead of 1. - Edge direction. The edges are undirected:
[[1, 0]]withn = 2returnstrue, just as[[0, 1]]would. - Right count, wrong shape. The third example has
n - 1edges, yet it holds a cycle and an isolated node. The count only rules out wrong totals; the union-find loop catches the cycle. - Disconnected graphs.
n = 4with[[0, 1], [2, 3]]returnsfalseby the count alone (2 edges instead of 3), andn = 3with[[0, 1]]returnsfalsetoo. - Skipping the count. Without it, the loop would accept a graph with fewer edges and no cycle, such as
[[0, 1]]for three nodes, though node 2 is cut off. - Comparing nodes instead of roots. Checking
edge[0] === edge[1]only catches an edge from a node to itself. The test must compare the roots of the groups. - Merging in the wrong direction. Hanging the larger group under the smaller still gives correct answers, but long chains can form and slow
finddown. - Recursion depth. A recursive
findor DFS can overflow the call stack on a path of 100,000 nodes. The loop infindhas no such limit: a path of 100,000 nodes returnstruewithout trouble.
Testing
n = 5,[[0, 1], [0, 2], [0, 3], [1, 4]]givestrue.n = 5,[[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]givesfalse.n = 4,[[0, 1], [1, 2], [2, 0]]givesfalse.n = 1,[]givestrue.n = 2,[]givesfalse.n = 2,[[1, 0]]givestrue.n = 4,[[0, 1], [2, 3]]givesfalse.n = 3,[[0, 1]]givesfalse.
