Populating Next Right Pointers: The Recursive Level-Link Trick
Wire every node's next pointer in a perfect binary tree using recursion and the parent's own next pointer — intuition, JavaScript code, and a walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most tree problems only care about parent-child links. This one asks you to add a sideways link: every node gets a next pointer to the node immediately to its right on the same level. It looks like a job for breadth-first search with a queue — walk each level, chain the nodes as you go.
But there's a sharper answer. In a perfect binary tree, the parent already knows everything a child needs. If you connect pointers top-down, each node can wire up its two children in O(1) using nothing but a pointer the parent set moments earlier. No queue, no explicit level tracking — just recursion.
That reframe is the whole problem, and it generalizes to any "use the layer above to build the layer below" tree question.
The problem
You're given the root of a perfect binary tree — every internal node has exactly two children, and all leaves sit on the same level. Each node has an extra field, next, that starts as null. Set every next pointer so it points to the node directly to its right on the same level. The rightmost node on each level keeps next = null.
Input tree (level-order): 1,2,3,4,5,6,7
1
/ \
2 3
/ \ / \
4 5 6 7
Output next pointers:
Level 0: 1 -> null
Level 1: 2 -> 3 -> null
Level 2: 4 -> 5 -> 6 -> 7 -> nullThe hard part is level 2: linking 4 -> 5 is easy because they share a parent, but 5 -> 6 crosses from parent 2 into parent 3. Handling that jump without walking the whole level is the crux.
The brute force baseline
The textbook approach is a BFS level-order traversal. Push each level into a queue, then chain the nodes inside it.
function connect(root) {
if (!root) return root;
const queue = [root];
while (queue.length > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
if (i < size - 1) node.next = queue[0]; // link to next in level
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return root;
}This is correct and O(n) time, but it carries a queue that holds up to n/2 nodes — the entire bottom level of a perfect tree. That's O(n) extra space. The LeetCode follow-up explicitly asks you to do better, using only the recursion stack. The queue is doing bookkeeping the tree structure already encodes for free.
The key insight: let the parent do the work
Here's the reframe. Instead of gathering a level and chaining it, ask a single node: "which of my descendants' next pointers can I set right now?"
A node curr can set exactly two links:
curr.left.next = curr.right— its own two children are siblings, so the left one's neighbor is the right one. Trivial.curr.right.next = curr.next.left— the right child's neighbor lives undercurr's next node. That's the cross-parent jump. It only works ifcurr.nextalready exists.
Condition 2 is why order matters. If you process the tree top-down, then by the time you reach curr, its parent already set curr.next on an earlier call. So curr.next.left is a valid pointer you can hop through — no queue required. The pointer you need on level k was manufactured while processing level k-1.
That's the pattern: each level links the level below it, using the sideways pointers it just received from above.
The optimal solution
This is exactly the algorithm the visualizer steps through. A recursive helper wires up curr's children, then recurses.
var connect = function (root) {
if (!root) return root;
let traversal = (curr) => {
if (curr.left) {
curr.left.next = curr.right;
}
if (curr.right && curr.next) {
curr.right.next = curr.next.left;
}
curr.left && traversal(curr.left);
curr.right && traversal(curr.right);
};
traversal(root);
return root;
};Read the two if blocks as the two links from the insight:
curr.left.next = curr.righthandles the easy same-parent case.curr.right.next = curr.next.lefthandles the cross-parent jump — guarded bycurr.nextso the rightmost node on each level (whosenextisnull) safely skips it.
Then it recurses left first, then right. Because the parent set both children's next pointers before descending, every node is fully prepared by the time its own call runs. The curr.left && short-circuits stop the recursion at the leaves.
Walkthrough
Trace connect on the tree 1,2,3,4,5,6,7. The next column shows the link created on that call.
| Call | curr | curr.next (set by parent) | Link 1: left.next = right | Link 2: right.next = curr.next.left |
|---|---|---|---|---|
| 1 | 1 | null | 2.next = 3 | skipped (curr.next is null) |
| 2 | 2 | 3 | 4.next = 5 | 5.next = 3.left = 6 |
| 3 | 4 | 5 | skipped (leaf) | skipped (leaf) |
| 4 | 5 | 6 | skipped (leaf) | skipped (leaf) |
| 5 | 3 | null | 6.next = 7 | skipped (curr.next is null) |
| 6 | 6 | 7 | skipped (leaf) | skipped (leaf) |
| 7 | 7 | null | skipped (leaf) | skipped (leaf) |
The recursion order is 1 → 2 → 4 → 5 → 3 → 6 → 7 (left subtree fully wired before the right). Watch call 2: it sets 5.next = 6 even though 5 and 6 live under different parents. That works only because call 1 already set 2.next = 3, so curr.next.left reaches into node 3's left child.
Collect the links: 2 -> 3 (level 1) and 4 -> 5 -> 6 -> 7 (level 2). Four next pointers, every level fully chained, no queue ever allocated.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | Each node is visited by exactly one recursive call doing O(1) pointer work. |
| Space | O(h) = O(log n) | The recursion stack holds one frame per level of the tree; height h ≈ log₂n for a perfect tree. |
This beats the BFS baseline's O(n) queue space. The recursion stack still grows with tree height, so it isn't the strict O(1) auxiliary space some interviewers push for — that requires an iterative solution that walks each level using the next pointers already built. But for a clean, readable answer that satisfies the "no data-structure" follow-up, the recursive version is the sweet spot.
Common mistakes
- Forgetting the
curr.nextguard. Writingcurr.right.next = curr.next.leftwithout checkingcurr.nextcrashes on the rightmost node of every level, wherecurr.nextisnull. - Recursing before linking. If you descend into children before setting their
nextpointers, the cross-parent hopcurr.next.leftreads a pointer that hasn't been set yet. Wire up both children first, then recurse. - Assuming it works on any binary tree. This exact code relies on the perfect tree guarantee —
curr.next.leftassumes the neighbor node has a left child. On a general tree with missing children (LeetCode 117), you need the variant that skips over gaps. - Reaching for a queue out of habit. BFS is correct but spends O(n) space the structure already gives you for free. The whole point of this problem is to notice the top-down pointer dependency.
Where this pattern shows up next
The "use the layer you already built to build the next one" idea, plus clean recursive tree traversal, powers a whole family of problems:
- Symmetric Tree — mirror-check two subtrees in lockstep, another paired-recursion trick.
- Symmetric Tree - Iterative — the same mirror check driven by an explicit stack instead of recursion.
- Same Tree — walk two trees together and compare structure node by node.
- Subtree of Another Tree — combine same-tree checking with a search over every node.
You can also step through the recursive next-pointer algorithm interactively to watch each next link snap into place, level by level.
FAQ
Why does the recursive solution avoid a queue?
Because a perfect binary tree already encodes the level structure through its shape. When you process nodes top-down, a parent sets curr.next before recursing, so each node can reach its right neighbor's subtree through curr.next.left. A BFS queue re-derives that same adjacency at O(n) space cost, but the pointers you build on one level give you everything you need to link the next level for free.
What is the space complexity of this approach?
O(h), where h is the height of the tree — about O(log n) for a perfect binary tree. The only extra memory is the recursion stack, which holds one frame per level as the calls descend. That's strictly better than the BFS solution's O(n) queue. A fully O(1) auxiliary-space solution exists too: iterate level by level, using the next pointers you've already established to traverse without any stack.
Why must the two links be set before recursing into the children?
The cross-parent link curr.right.next = curr.next.left depends on curr.next already being set by curr's parent. If you recursed into a child before that child received its own next pointer, the child's cross-parent hop would read a null or stale pointer. Setting both children's links first, then descending, guarantees every node finds its next pointer already populated when its call runs.
Does this code work on a non-perfect binary tree?
No. It assumes every internal node has two children and that curr.next.left always exists, which only holds for a perfect tree (LeetCode 116). On a tree with missing nodes (LeetCode 117, "Populating Next Right Pointers II"), the right neighbor might be several nodes over, or the neighbor's children might be absent. That variant needs logic to scan across the parent level and skip gaps before linking.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.