Populating Next Right Pointers in Each Node
Understanding the Problem
We have a perfect binary tree, meaning every internal node has exactly two children and all leaves sit at the same depth. Each node has an extra next pointer that we need to wire up so it points to the node immediately to its right on the same level. The rightmost node on each level should have next = null.
The "perfect binary tree" guarantee is what makes this problem tractable. Every level is completely full, so we can predict which nodes are neighbors on each level without handling missing children or uneven subtrees. The general version, where the tree can have any shape, is harder because a node's right neighbor on the same level might be several subtrees away.
Two kinds of connections need to be made: nodes that share a parent (like 4 and 5) and nodes that have different parents (like 5 and 6). The second kind is what the algorithm has to be careful about.
Key Constraints:
Number of nodes in range [0, 2^12 - 1]. Up to 4095 nodes, small enough that any O(n) approach is fast. Time is not the constraint here.- The follow-up asks for O(1) extra space. That is the real target, and it shapes the third approach below.
Perfect binary tree. If a node has a left child, it has a right child too, and a node's neighbor on the same level always has children when this node does. This regularity is what makes the O(1) space approach possible.
Approach 1: BFS with Queue (Level-Order Traversal)
Intuition
We need to connect nodes on the same level, and BFS processes nodes one level at a time. A standard level-order traversal with a queue lets us link consecutive nodes as we go.
We process the queue one level at a time, recording the level's size before we start. For each node except the last on that level, we set its next pointer to the node now at the front of the queue, which is its right neighbor. The last node on each level keeps next = null.
Algorithm
- If the root is null, return null.
- Initialize a queue and add the root.
- While the queue is not empty, record the current level's size.
- For each node at this level, dequeue it and set its next pointer to the front of the queue (unless it's the last node on this level).
- Enqueue the node's left and right children if they exist.
- Return the root.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once during the BFS traversal. Each node is enqueued and dequeued once, and we do O(1) work per node (setting the next pointer, adding children).
- Space Complexity: O(n). The queue can hold up to n/2 nodes at the widest level of a perfect binary tree (the leaf level). For a tree with n nodes, the last level has roughly (n+1)/2 nodes.
BFS works but the queue costs O(n) extra space. The next approach drops the queue by using recursion, relying on a parent's next pointer being set before we reach its children.
Approach 2: DFS (Recursive Pre-Order)
Intuition
From any node, there are exactly two next connections to make among its children:
- Same-parent connection: The left child's
nextpoints to the right child. Both children belong to the same node, so this is a direct assignment. - Cross-parent connection: The right child's
nextpoints to the left child of the parent'snextnode, for example 5 points to 6 because 5's parent (2) hasnextpointing to 3, and 3's left child is 6.
The cross-parent connection depends on the parent's next already being set. Processing the tree in pre-order (node, then left subtree, then right subtree) provides that ordering: a node's next is wired up while we process its parent, before we ever descend into the node itself.
When we process a node, its own next is already correct. The root has next = null from the start. For any other node, its next was assigned while we processed its parent (one of the two connection lines above), and the parent was processed before this node because pre-order visits a node before its subtrees. So node.next.left is always a valid neighbor when node.next is not null.
Algorithm
- If the root is null or has no children, return (base case).
- Connect left child to right child:
node.left.next = node.right. - If the current node has a next pointer, connect the right child across:
node.right.next = node.next.left. - Recurse on the left subtree, then the right subtree.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once. Each visit does O(1) work (two pointer assignments and two recursive calls).
- Space Complexity: O(log n). The recursion stack goes as deep as the height of the tree. Because the tree is perfect, its height is log(n), so the stack never exceeds that. The problem states recursive stack space does not count as extra space, so this counts as O(1) by the problem's definition.
The recursive version still uses the call stack. The next approach removes it entirely: once a level's next pointers are set, that level acts as a linked list we can walk to connect the level below.
Approach 3: Iterative Using Previously Established Next Pointers (Optimal)
Intuition
This is the approach the follow-up is hinting at. Once all the next pointers on level k are connected, level k is a linked list. We can walk it using those next pointers and, as we go, connect every node on level k+1. No queue, no recursion, two pointers.
We start at the root (level 0) and move down. At each level we traverse left to right using the next pointers, wiring up the children below us. The same two connections apply: same-parent (left child to right child) and cross-parent (right child to the next node's left child).
We process levels strictly top-down. Level 1's next pointers are set while we traverse level 0, level 2's while we traverse level 1, and so on. So by the time we walk level k to connect level k+1, level k's pointers are already in place. The root needs no next because it is alone on level 0.
This relies on the tree being perfect. Every internal node has both children, so leftmost.left reliably tells us whether another level exists, and current.next.left always exists when current.next does. A general binary tree would need extra handling for missing children.
Algorithm
- Start with a pointer
leftmostat the root. This tracks the leftmost node of the current level. - While
leftmost.leftis not null (there is a next level to connect): - Set
current = leftmostto traverse the current level. - While
currentis not null: - Connect same-parent:
current.left.next = current.right. - Connect cross-parent: if
current.nextexists,current.right.next = current.next.left. - Move to the next node on this level:
current = current.next. - Move
leftmostdown to the next level:leftmost = leftmost.left. - Return the root.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once. The outer loop runs O(log n) times (once per level), and the inner loop visits every node on that level. Across all levels, that's n total node visits.
- Space Complexity: O(1). We only use two pointers (
leftmostandcurrent). No queue, no recursion stack. This satisfies the follow-up constraint.