Populating Next Right Pointers
Populating Next Right Pointers: in a perfect binary tree, point every node's next at its right neighbour on the same level.
- The number of nodes in the tree is in the range [0, 2¹² - 1].
- -1000 <= Node.val <= 1000
Intuition
The task of populating next right pointers in a perfect binary tree is to give every node a pointer to its right neighbour on the same level, with the last node on each level pointing to null.
A level-order BFS solves this immediately — process a level, link each node to the next in the queue — and it is the right first answer. But it costs O(n) space for the queue, and the follow-up asks for constant extra space.
The insight that gets you there is that once a level is fully linked, it is a linked list, and you can walk that list without a queue. So use the level you have already wired as the rails for wiring the level below it. Start at the root, which is a trivially complete level of one, and work downward.
While walking a level, each node wires two connections in the level beneath:
- Its own children: node.left.next = node.right.
- The gap across to the neighbouring subtree: node.right.next = node.next.left.
That second link is the one people miss, and it is the reason the tree must be perfect. Because every internal node has exactly two children and all leaves are on the same level, node.next.left is guaranteed to exist whenever node.next does. On a merely complete or arbitrary tree that assumption fails and the problem needs a different approach.
The O(1)-space trick: once a level is threaded by next pointers, it acts as a linked list you can walk to wire the level below — no queue needed. Whenever a structure already contains the traversal order you were about to build a container for, use the structure. This only works because the tree is perfect, which guarantees every node has both children.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(1) space.
Use the finished level as rails
Keep a pointer to the leftmost node of the current level. Walk that level through the next pointers you already set, wiring the level below as you go. The already-linked level replaces the BFS queue, which is what brings the extra space down to O(1).
Link each node's own two children
For the node you are standing on, set node.left.next = node.right. This is the easy connection — both nodes share a parent, so the link is available directly without looking anywhere else.
Bridge the gap between subtrees
Set node.right.next = node.next.left when node.next exists. This joins the rightmost node of one subtree to the leftmost of the next, and it is the connection that makes the level continuous rather than a series of disconnected pairs.
Descend to the leftmost child
After walking a level to its end, move to the leftmost node of the next level — which is the current level's first node's left child. Repeat until you reach a node with no children, meaning the leaf level, which needs no wiring.
Rely on the tree being perfect
Every internal node having two children is what guarantees node.next.left exists whenever node.next does. On a non-perfect tree this dereference fails, and the general version of the problem needs a dummy-head technique to skip missing children.
Cost of the wiring
Every node is visited once and does O(1) work, giving O(n) time and genuinely O(1) extra space — only a couple of pointers, no queue and no recursion. That space bound is the entire reason to prefer this over the straightforward BFS.
Solution & live demo
Common pitfalls
Using a BFS queue
q = deque([root])
while q:
for _ in range(len(q)): ...while leftmost and leftmost.left:
head = leftmost
while head: ...Correct, but the follow-up asks for constant extra space and a queue holds up to n/2 nodes. The next pointers you just wired on the level above give you the same traversal for free.
Forgetting the cross-node link
head.left.next = head.right
head.left.next = head.right
if head.next:
head.right.next = head.next.leftWiring only within a parent leaves the level broken into disconnected pairs, so the next iteration can't walk across it. The gap between one parent's right child and the next parent's left child has to be bridged too.
Looping while leftmost alone is non-null
while leftmost:
while leftmost and leftmost.left:
On the last level there are no children to wire, and head.left.next raises. Checking for a left child confirms another level exists before trying to thread it.
Edge cases
parent.next.left may not exist — needs a scan for the next available child; this version relies on perfection.
Return immediately.