Coding · Trees
Populating Next Right Pointers in Each Node
- Reported once
- Medium
- SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Take a perfect binary tree given as a level-order array: every parent has two children and every leaf sits at the same depth. Set each node's next pointer to the node immediately to its right on the same level, or null for the last node of a level. To make the result checkable, the function returns the values reached by following next pointers level by level, with the string "#" ending each level, so [1,2,3,4,5,6,7] gives [1,"#",2,3,"#",4,5,6,7,"#"]. Aim for constant extra space, not counting the tree itself.
Restated in our own words, not a quote from Microsoft or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I start by confirming the tree is perfect: every parent has two children and every leaf is at the same depth. That shape is what lets one simple loop work, so if the tree can be ragged I need a different loop. Then I ask how large the tree can get, whether the pointers must be set on the existing nodes, whether extra space beyond a few variables is acceptable, and what to return for an empty tree.
My stated assumptions: the tree is perfect, values may repeat or be negative and are never compared, pointers are set in place, constant extra space is the goal, and an empty tree gives an empty result. A queue-based version is my fallback if the shape turns out to be irregular.
Brute force
Say the obvious answer and why it is too slow.
The obvious solution is a level-order traversal with a queue. At each level I note how many nodes are queued, pop that many, and link each popped node to the one behind it in the queue. The time is O(n), which is already the best possible, but the extra space is O(w) where w is the widest level. In a perfect tree the last level holds about half of all nodes, so the queue grows to roughly n/2 entries. For a tree with hundreds of thousands of nodes that is a real allocation, and the usual follow-up is to do it without the queue. A recursive version that sets left.next = right and right.next = node.next.left avoids the queue, but it costs O(h) call-stack space, which is small for a balanced tree and still not constant.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n) time, O(n) queue
- Time
- O(n)
- Space
- O(1) extra
The pattern is tree BFS by level, with the previous level doing the job of the queue. Once every node on one level has a correct next pointer, those pointers form a linked list across the level. Walking that list is a free level-order traversal, so no separate queue is needed.
While standing on a node of level d, I wire up its children on level d+1. The two children of one parent link directly: node.left.next = node.right. The right child has to reach into the neighbouring subtree, and the neighbour is already known: node.next is the parent's right sibling, so its left child is the right child's next. If node.next is null, this parent is last on its row and the right child keeps a null next.
The invariant is that when I begin level d, all of level d is already linked left to right. The root level is linked trivially, and processing a level establishes the same fact for the level below. To go down a level I follow left from the leftmost node, which exists on every level of a perfect tree. The loop ends when the leftmost node has no left child, because then the next level does not exist.
Out loud I say: each node on this row wires its own children, the parent's sibling gives the cousin link, and the finished row is the queue for the next one. Every node is visited once and I keep only two pointers, so the extra space is constant.
Walk it through
A dry run on the example, step by step.
| step | leftmost | node | links set | linked so far |
|---|---|---|---|---|
| 0 | 1 (root) | - | none yet | level 1: 1 |
| 1 | 1 | 1 | 2.next=3 | level 2: 2,3 |
| 2 | 2 | 2 | 4.next=5, 5.next=6 | level 3: 4,5,6 |
| 3 | 2 | 3 | 6.next=7 | level 3: 4,5,6,7 |
| 4 | 4 | - | no left child, stop | all levels linked |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take [1,2,3,4,5,6,7] and read the trace from top to bottom. With leftmost at 1 there is a single node, so it sets 2.next to 3 and has no neighbour. Then leftmost drops to 2, and the row 2, 3 is already linked. Node 2 links 4 to 5, and because 2.next is 3 it also links 5 to 6, the link that crosses between parents. Node 3 links 6 to 7 and has no neighbour. Now leftmost is 4, which has no left child, so the loop stops. The reading pass starts at 1, then 2 and 3, then 4 to 7, writing a marker after each row. The result is the list from the prompt, and each link in the table appears exactly when it is created.
The code
Runnable JavaScript, checked against test cases.
function connectLevels(values) {
const nodes = values.map((val) => ({ val, left: null, right: null, next: null }));
nodes.forEach((node, index) => {
node.left = nodes[2 * index + 1] ?? null;
node.right = nodes[2 * index + 2] ?? null;
});
const root = nodes[0] ?? null;
for (let leftmost = root; leftmost && leftmost.left; leftmost = leftmost.left) {
for (let node = leftmost; node; node = node.next) {
node.left.next = node.right;
if (node.next) node.right.next = node.next.left;
}
}
const rows = [];
for (let leftmost = root; leftmost; leftmost = leftmost.left) {
for (let node = leftmost; node; node = node.next) rows.push(node.val);
rows.push("#");
}
return rows;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Empty array: the root is null, both loops are skipped, and the result is an empty list.
- One node: the root has no left child, so no link is made and the output is the value followed by one marker.
- Last node of a row: its right child gets no cross link because
node.nextis null, so that pointer stays null. - Falsy values: a value of 0 is harmless because every loop tests node objects and never the values.
- Not a perfect tree: a missing child would make
node.left.nextfail. For ragged trees use a dummy head that walks each level and links whichever children exist.
Follow-ups to expect
Where the interviewer pushes next.
- How would you change the loop if the tree is not perfect and children can be missing?
- Can you do it recursively, and what does the recursion cost in space?
- How would the same next pointers give you the right-side view of the tree?
- How would you link each node to its left neighbour instead?
- How does the approach change for a tree where each node has many children?
Where candidates slip
The mistakes this problem punishes.
- Linking only the two children of the same parent and forgetting the cross-parent link, so 5 points to null instead of 6.
- Moving down with
leftmost = leftmost.nextinstead ofleftmost.left. - Dereferencing
leftmost.lefton the leaf row without checking that it exists. - Writing
node.next.leftwithout checking thatnode.nextis set, which fails on the last node of every row. - Copying each level into a temporary array before linking: it is correct but quietly uses O(n) memory.
- Using a queue and still calling the answer constant space.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.