Populating Next Right Pointers
In a perfect binary tree, point every node's next at its right neighbour on the same level.
Intuition
Once a level is linked, it becomes a linked list you can walk to wire the level below — no queue needed. A node's children link as left→right; the gap across subtrees bridges via the parent's next: node.right.next = node.next.left.
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
Use the level above as rails
Walk level L via next pointers while connecting level L+1 — O(1) extra space, unlike BFS's queue.
Two wire types
Same parent: left.next = right. Across parents: right.next = parent.next.left (exists because the tree is perfect).
Descend leftmost
After finishing a level, drop to its leftmost node and repeat until leaves.
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.