Graph Valid Tree (LeetCode 261)
What a tree is (assume nothing): a tree is an undirected graph in which every node can reach every other node, and no cycle exists. A cycle is a path of edges that starts and ends at the same node without using an edge twice.
You get n, the number of nodes, numbered 0 to n - 1. You also get edges, a list of pairs. Each pair [a, b] is an undirected edge: it joins node a and node b, and it can be walked in both directions.
Return true when these edges make one tree. Return false otherwise.
Worked Examples
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]true0 joins nodes 1, 2 and 3, and node 1 joins node 4. All five nodes are in one group and no edge closes a loop.n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]false[1,2], [2,3] and [1,3] form a loop through nodes 1, 2 and 3, so this graph is not a tree.⚖️Formal Constraints & Bounds
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 20 <= ai, bi < nai != biThere are no self-loops or repeated edges.
Core Insight
Remember the node each step came from. The edge back to that node is the edge just used, so skip it. Any other edge to a seen node is a second route and closes a cycle. A tree also needs every node reached, so the answer ends with reached == n.
Real-World Scenario & Production Applications
A company joins its offices with cables. Every office must be reachable from every other office, and the cables must not form a loop. A loop is a wasted cable, and a missing connection is an office that cannot be reached. This check finds both problems.
Step-by-Step Execution Trace Table
Trace of Example 2: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]. The lists are adj[0] = [1], adj[1] = [0, 2, 3, 4], adj[2] = [1, 3], adj[3] = [2, 1] and adj[4] = [1]. The search starts with seen[0] = True, reached = 1 and stack = [(0, -1)].
| Step | Pop (u, parent) | v | What happens | reached | stack after |
|---|---|---|---|---|---|
| 1 | (0, -1) | 1 | 1 is new: seen[1] = True, push (1, 0) | 2 | [(1, 0)] |
| 2 | (1, 0) | 0 | 0 is the parent: skip | 2 | [] |
| 3 | (1, 0) | 2 | 2 is new: push (2, 1) | 3 | [(2, 1)] |
| 4 | (1, 0) | 3 | 3 is new: push (3, 1) | 4 | [(2, 1), (3, 1)] |
| 5 | (1, 0) | 4 | 4 is new: push (4, 1) | 5 | [(2, 1), (3, 1), (4, 1)] |
| 6 | (4, 1) | 1 | 1 is the parent: skip | 5 | [(2, 1), (3, 1)] |
| 7 | (3, 1) | 2 | 2 is seen and is not the parent 1: cycle, return False | 5 | [(2, 1)] |
Node 2 was reached from node 1 by the edge [1,2], and node 3 was reached from node 1 by the edge [1,3]. The edge [2,3] joins them a second time, so it closes the cycle 1, 2, 3. In Example 1 the search ends with reached = 5 and no cycle, so the answer is True.
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]trueTrace of Example 2: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]. The lists are adj[0] = [1], adj[1] = [0, 2, 3, 4], adj[2] = [1, 3], adj[3] = [2, 1] and adj[4] = [1]. The search starts with seen[0] = True, reached = 1 and stack = [(0, -1)].
| Step | Pop (u, parent) | v | What happens | reached | stack after |
|---|---|---|---|---|---|
| 1 | (0, -1) | 1 | 1 is new: seen[1] = True, push (1, 0) | 2 | [(1, 0)] |
| 2 | (1, 0) | 0 | 0 is the parent: skip | 2 | [] |
| 3 | (1, 0) | 2 | 2 is new: push (2, 1) | 3 | [(2, 1)] |
| 4 | (1, 0) | 3 | 3 is new: push (3, 1) | 4 | [(2, 1), (3, 1)] |
| 5 | (1, 0) | 4 | 4 is new: push (4, 1) | 5 | [(2, 1), (3, 1), (4, 1)] |
| 6 | (4, 1) | 1 | 1 is the parent: skip | 5 | [(2, 1), (3, 1)] |
| 7 | (3, 1) | 2 | 2 is seen and is not the parent 1: cycle, return False | 5 | [(2, 1)] |
Node 2 was reached from node 1 by the edge [1,2], and node 3 was reached from node 1 by the edge [1,3]. The edge [2,3] joins them a second time, so it closes the cycle 1, 2, 3. In Example 1 the search ends with reached = 5 and no cycle, so the answer is True.
| 1 | adj = [[] for _ in range(n)] |
| 2 | for u, v in edges: |
| 3 | adj[u].append(v) |
| 4 | adj[v].append(u) |
| 5 | seen = [False] * n |
| 6 | seen[0] = True |
| 7 | reached = 1 |
| 8 | stack = [(0, -1)] |
| 9 | while stack: |
| 10 | u, parent = stack.pop() |
| 11 | for v in adj[u]: |
| 12 | if v == parent: |
| 13 | continue |
| 14 | if seen[v]: |
| 15 | return False |
| 16 | seen[v] = True |
| 17 | reached += 1 |
| 18 | stack.append((v, u)) |
| 19 | return reached == n |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A tree is an undirected graph in which every node can reach every other node, and no cycle exists. A cycle is a path of edges that starts and ends at the same node without using an edge twice.
validTree checks both parts with one search that starts at node 0. The search keeps a stack of pairs. Each pair holds a node and the node it was reached from, called its parent.
🔌 Example: Cables Between Offices
Think of the nodes as offices and the edges as cables. You walk from office to office along the cables and write down each office you reach. When you stand in office u and look at its cables, one cable leads back to the office you just came from. That cable is not a problem, because it is the way you came. If any other cable leads to an office that is already on your list, you have found a second way to reach that office, so the cables form a loop.
🔑 The Key Idea in the Code
if v == parent: continue skips the cable you came by. if seen[v]: return False handles every other cable to a seen node. Without the first line, the cable back to parent would look like a loop, and every graph that has an edge would fail. return reached == n is the second half of the check. A graph with no loop but with separate groups is not a tree.
Returning the edge the search meets first: the search finds the cycle at one edge, but the answer is the cycle edge that comes last in
edges. Foredges = [[1,2],[2,3],[3,4],[1,4],[1,5]], the search meets[2,3]first and the answer is[1,4].Allocating
adjwithnslots: the nodes are numbered from 1 ton, soadj[n]does not exist and raises an IndexError. Usen + 1slots and leave slot 0 empty.Searching with recursion: a path of 1000 nodes plus one extra edge needs about 1000 nested calls. That reaches Python's default recursion limit of 1000 and raises a RecursionError. The explicit
stackhas no such limit.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks whether n nodes and a list of undirected edges make "a valid tree". A tree is a graph with no cycle in which every node is connected, so the question has two parts: no cycle, and one connected group. The cycle part is an undirected cycle check with a parent skip.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
seen[u] is True once the search has reached u, and each seen node was reached once, from its parent. Every edge scanned so far either reached a new node or led back to parent. Any other edge to a seen node returns False. At the end, reached counts the nodes the search from node 0 reached.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if v == parent: continue: without it, the edge back toparentfindsparentalready inseen.validTree(2, [[0, 1]])returnsFalsefor a graph that is a tree.return reached == n:return Truehere accepts a forest.validTree(4, [[0, 1], [2, 3]])returnsTrueinstead ofFalse.reached = 1before the loop: node 0 counts as reached. Withreached = 0, a tree ends one short, and Example 1 returnsFalse.n = 1, edges = []: node 0 alone is a tree. The loop does not run, andreached == nis1 == 1, so the answer isTrue.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with a cycle check that remembers the parent. A tree is a graph with no cycle in which every node is connected, so I check both parts. I start one search at node 0 with a stack. Each stack entry holds a node and the node it came from. When I scan a neighbour, I first skip the node I came from, because that edge is the one I just used. If the neighbour is any other node that is already seen, there are two routes between those nodes, so there is a cycle, and I return false. Otherwise I mark the neighbour seen, count it and push it. When the stack is empty, I return whether the count of reached nodes equals n. If it is smaller, some nodes are in another group. Each node and each edge is handled a constant number of times, so time is order V plus E, and space is order V plus E for the adjacency list.
Complexity & Mathematical Proof
O(V + E)
Look at the code. Building adj reads each of the E edges once and appends two entries, so it takes O(E). A node enters stack only when seen[v] is False, and then seen[v] becomes True. So each node is pushed at most once, and stack.pop() runs at most V times. Each pop scans adj[u] once. Over the whole run, the scans read every adjacency entry once, which is 2E entries with constant work each. Total: O(V + E).
O(V + E)
adj holds V lists with 2E entries in total. seen holds V flags. stack holds at most V entries, because each node is pushed once. There is no recursion, so the call stack is O(1). The total is O(V + E).
T(V, E) = E (build adj) + V (pops) + 2E (adjacency entries) = O(V + E)
Derivation Progression
E edges, 2 appends each = O(E)
for u, v in edges reads each edge once and stores it at both ends.
seen[v] is set before the push: at most V pops
A node is pushed only when seen[v] is False, and the push sets it to True.
sum of len(adj[u]) over popped nodes = 2E
Every edge sits in two lists and each list is scanned once, with constant work per entry: the parent test, the seen test, the push.
Variable Definitions
Number of nodes, n
Number of edges, len(edges); the adjacency lists hold 2E entries in total
Memory Architecture & Bounds
O(1): an explicit stack, no recursion
O(V + E): adj has 2E entries, seen has V flags and stack never holds more than V entries
O(1): one boolean
Boundary Best / Worst Cases
for the build, but the search can stop early: the first extra edge to a seen node returns False at once.
.
: a tree, where every node is pushed and every edge is read before return reached == n.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "valid tree", "undirected edges". A tree is a graph with no cycle in which every node is connected, so one search from node 0 answers both parts. An edge to a seen node that is not the parent is a cycle, and the count of reached nodes shows whether the graph is connected.
and at most edges, so one search is , about steps. A recursive search can be calls deep, which passes Python's default limit of , so the code uses an explicit stack. There are no repeated edges and no self-loops, so each pair of nodes appears at most once.
Dropping if v == parent: continue reports a cycle on every edge: validTree(2, [[0, 1]]) returns False. Ending with return True instead of return reached == n accepts a forest: validTree(4, [[0, 1], [2, 3]]) returns True. Starting reached at 0 undercounts by one, so Example 1 returns False.
Core Algorithmic State Invariants
- Example 2, One Skip And One Cycle
The search skips the edge from node 1 back to its parent 0, and it pushes nodes 2, 3 and 4 with parent 1. Popping node 3, its neighbour 2 is already seen and is not its parent 1. So the edge 3-2 closes a cycle, and the answer is false.
- Example 1, No Cycle
Every edge back to a parent is skipped, and no other edge reaches a seen node. The search ends with reached = 5. That equals n, so the answer is true.
- No Cycle Is Not Enough
In n = 4, edges = [[0,1],[2,3]], no edge closes a cycle. The search from node 0 reaches only nodes 0 and 1, so reached = 2 is not n = 4. The answer is false: the nodes form two separate groups.
Graph Valid Tree (LeetCode 261)
What a tree is (assume nothing): a tree is an undirected graph in which every node can reach every other node, and no cycle exists. A cycle is a path of edges that starts and ends at the same node without using an edge twice.
You get n, the number of nodes, numbered 0 to n - 1. You also get edges, a list of pairs. Each pair [a, b] is an undirected edge: it joins node a and node b, and it can be walked in both directions.
Return true when these edges make one tree. Return false otherwise.
Worked Examples
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]true0 joins nodes 1, 2 and 3, and node 1 joins node 4. All five nodes are in one group and no edge closes a loop.n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]false[1,2], [2,3] and [1,3] form a loop through nodes 1, 2 and 3, so this graph is not a tree.⚖️Formal Constraints & Bounds
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 20 <= ai, bi < nai != biThere are no self-loops or repeated edges.
Core Insight
Remember the node each step came from. The edge back to that node is the edge just used, so skip it. Any other edge to a seen node is a second route and closes a cycle. A tree also needs every node reached, so the answer ends with reached == n.
Real-World Scenario & Production Applications
A company joins its offices with cables. Every office must be reachable from every other office, and the cables must not form a loop. A loop is a wasted cable, and a missing connection is an office that cannot be reached. This check finds both problems.
Step-by-Step Execution Trace Table
Trace of Example 2: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]. The lists are adj[0] = [1], adj[1] = [0, 2, 3, 4], adj[2] = [1, 3], adj[3] = [2, 1] and adj[4] = [1]. The search starts with seen[0] = True, reached = 1 and stack = [(0, -1)].
| Step | Pop (u, parent) | v | What happens | reached | stack after |
|---|---|---|---|---|---|
| 1 | (0, -1) | 1 | 1 is new: seen[1] = True, push (1, 0) | 2 | [(1, 0)] |
| 2 | (1, 0) | 0 | 0 is the parent: skip | 2 | [] |
| 3 | (1, 0) | 2 | 2 is new: push (2, 1) | 3 | [(2, 1)] |
| 4 | (1, 0) | 3 | 3 is new: push (3, 1) | 4 | [(2, 1), (3, 1)] |
| 5 | (1, 0) | 4 | 4 is new: push (4, 1) | 5 | [(2, 1), (3, 1), (4, 1)] |
| 6 | (4, 1) | 1 | 1 is the parent: skip | 5 | [(2, 1), (3, 1)] |
| 7 | (3, 1) | 2 | 2 is seen and is not the parent 1: cycle, return False | 5 | [(2, 1)] |
Node 2 was reached from node 1 by the edge [1,2], and node 3 was reached from node 1 by the edge [1,3]. The edge [2,3] joins them a second time, so it closes the cycle 1, 2, 3. In Example 1 the search ends with reached = 5 and no cycle, so the answer is True.
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]trueTrace of Example 2: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]. The lists are adj[0] = [1], adj[1] = [0, 2, 3, 4], adj[2] = [1, 3], adj[3] = [2, 1] and adj[4] = [1]. The search starts with seen[0] = True, reached = 1 and stack = [(0, -1)].
| Step | Pop (u, parent) | v | What happens | reached | stack after |
|---|---|---|---|---|---|
| 1 | (0, -1) | 1 | 1 is new: seen[1] = True, push (1, 0) | 2 | [(1, 0)] |
| 2 | (1, 0) | 0 | 0 is the parent: skip | 2 | [] |
| 3 | (1, 0) | 2 | 2 is new: push (2, 1) | 3 | [(2, 1)] |
| 4 | (1, 0) | 3 | 3 is new: push (3, 1) | 4 | [(2, 1), (3, 1)] |
| 5 | (1, 0) | 4 | 4 is new: push (4, 1) | 5 | [(2, 1), (3, 1), (4, 1)] |
| 6 | (4, 1) | 1 | 1 is the parent: skip | 5 | [(2, 1), (3, 1)] |
| 7 | (3, 1) | 2 | 2 is seen and is not the parent 1: cycle, return False | 5 | [(2, 1)] |
Node 2 was reached from node 1 by the edge [1,2], and node 3 was reached from node 1 by the edge [1,3]. The edge [2,3] joins them a second time, so it closes the cycle 1, 2, 3. In Example 1 the search ends with reached = 5 and no cycle, so the answer is True.
| 1 | adj = [[] for _ in range(n)] |
| 2 | for u, v in edges: |
| 3 | adj[u].append(v) |
| 4 | adj[v].append(u) |
| 5 | seen = [False] * n |
| 6 | seen[0] = True |
| 7 | reached = 1 |
| 8 | stack = [(0, -1)] |
| 9 | while stack: |
| 10 | u, parent = stack.pop() |
| 11 | for v in adj[u]: |
| 12 | if v == parent: |
| 13 | continue |
| 14 | if seen[v]: |
| 15 | return False |
| 16 | seen[v] = True |
| 17 | reached += 1 |
| 18 | stack.append((v, u)) |
| 19 | return reached == n |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A tree is an undirected graph in which every node can reach every other node, and no cycle exists. A cycle is a path of edges that starts and ends at the same node without using an edge twice.
validTree checks both parts with one search that starts at node 0. The search keeps a stack of pairs. Each pair holds a node and the node it was reached from, called its parent.
🔌 Example: Cables Between Offices
Think of the nodes as offices and the edges as cables. You walk from office to office along the cables and write down each office you reach. When you stand in office u and look at its cables, one cable leads back to the office you just came from. That cable is not a problem, because it is the way you came. If any other cable leads to an office that is already on your list, you have found a second way to reach that office, so the cables form a loop.
🔑 The Key Idea in the Code
if v == parent: continue skips the cable you came by. if seen[v]: return False handles every other cable to a seen node. Without the first line, the cable back to parent would look like a loop, and every graph that has an edge would fail. return reached == n is the second half of the check. A graph with no loop but with separate groups is not a tree.
Returning the edge the search meets first: the search finds the cycle at one edge, but the answer is the cycle edge that comes last in
edges. Foredges = [[1,2],[2,3],[3,4],[1,4],[1,5]], the search meets[2,3]first and the answer is[1,4].Allocating
adjwithnslots: the nodes are numbered from 1 ton, soadj[n]does not exist and raises an IndexError. Usen + 1slots and leave slot 0 empty.Searching with recursion: a path of 1000 nodes plus one extra edge needs about 1000 nested calls. That reaches Python's default recursion limit of 1000 and raises a RecursionError. The explicit
stackhas no such limit.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks whether n nodes and a list of undirected edges make "a valid tree". A tree is a graph with no cycle in which every node is connected, so the question has two parts: no cycle, and one connected group. The cycle part is an undirected cycle check with a parent skip.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
seen[u] is True once the search has reached u, and each seen node was reached once, from its parent. Every edge scanned so far either reached a new node or led back to parent. Any other edge to a seen node returns False. At the end, reached counts the nodes the search from node 0 reached.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if v == parent: continue: without it, the edge back toparentfindsparentalready inseen.validTree(2, [[0, 1]])returnsFalsefor a graph that is a tree.return reached == n:return Truehere accepts a forest.validTree(4, [[0, 1], [2, 3]])returnsTrueinstead ofFalse.reached = 1before the loop: node 0 counts as reached. Withreached = 0, a tree ends one short, and Example 1 returnsFalse.n = 1, edges = []: node 0 alone is a tree. The loop does not run, andreached == nis1 == 1, so the answer isTrue.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with a cycle check that remembers the parent. A tree is a graph with no cycle in which every node is connected, so I check both parts. I start one search at node 0 with a stack. Each stack entry holds a node and the node it came from. When I scan a neighbour, I first skip the node I came from, because that edge is the one I just used. If the neighbour is any other node that is already seen, there are two routes between those nodes, so there is a cycle, and I return false. Otherwise I mark the neighbour seen, count it and push it. When the stack is empty, I return whether the count of reached nodes equals n. If it is smaller, some nodes are in another group. Each node and each edge is handled a constant number of times, so time is order V plus E, and space is order V plus E for the adjacency list.
Complexity & Mathematical Proof
O(V + E)
Look at the code. Building adj reads each of the E edges once and appends two entries, so it takes O(E). A node enters stack only when seen[v] is False, and then seen[v] becomes True. So each node is pushed at most once, and stack.pop() runs at most V times. Each pop scans adj[u] once. Over the whole run, the scans read every adjacency entry once, which is 2E entries with constant work each. Total: O(V + E).
O(V + E)
adj holds V lists with 2E entries in total. seen holds V flags. stack holds at most V entries, because each node is pushed once. There is no recursion, so the call stack is O(1). The total is O(V + E).
T(V, E) = E (build adj) + V (pops) + 2E (adjacency entries) = O(V + E)
Derivation Progression
E edges, 2 appends each = O(E)
for u, v in edges reads each edge once and stores it at both ends.
seen[v] is set before the push: at most V pops
A node is pushed only when seen[v] is False, and the push sets it to True.
sum of len(adj[u]) over popped nodes = 2E
Every edge sits in two lists and each list is scanned once, with constant work per entry: the parent test, the seen test, the push.
Variable Definitions
Number of nodes, n
Number of edges, len(edges); the adjacency lists hold 2E entries in total
Memory Architecture & Bounds
O(1): an explicit stack, no recursion
O(V + E): adj has 2E entries, seen has V flags and stack never holds more than V entries
O(1): one boolean
Boundary Best / Worst Cases
for the build, but the search can stop early: the first extra edge to a seen node returns False at once.
.
: a tree, where every node is pushed and every edge is read before return reached == n.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "valid tree", "undirected edges". A tree is a graph with no cycle in which every node is connected, so one search from node 0 answers both parts. An edge to a seen node that is not the parent is a cycle, and the count of reached nodes shows whether the graph is connected.
and at most edges, so one search is , about steps. A recursive search can be calls deep, which passes Python's default limit of , so the code uses an explicit stack. There are no repeated edges and no self-loops, so each pair of nodes appears at most once.
Dropping if v == parent: continue reports a cycle on every edge: validTree(2, [[0, 1]]) returns False. Ending with return True instead of return reached == n accepts a forest: validTree(4, [[0, 1], [2, 3]]) returns True. Starting reached at 0 undercounts by one, so Example 1 returns False.
Core Algorithmic State Invariants
- Example 2, One Skip And One Cycle
The search skips the edge from node 1 back to its parent 0, and it pushes nodes 2, 3 and 4 with parent 1. Popping node 3, its neighbour 2 is already seen and is not its parent 1. So the edge 3-2 closes a cycle, and the answer is false.
- Example 1, No Cycle
Every edge back to a parent is skipped, and no other edge reaches a seen node. The search ends with reached = 5. That equals n, so the answer is true.
- No Cycle Is Not Enough
In n = 4, edges = [[0,1],[2,3]], no edge closes a cycle. The search from node 0 reaches only nodes 0 and 1, so reached = 2 is not n = 4. The answer is false: the nodes form two separate groups.