Populating Next Right Pointers
In a perfect binary tree, point every node's next at its right neighbour on the same level.
02
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.
03
Approach
1
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.
2
Two wire types
Same parent: left.next = right. Across parents: right.next = parent.next.left (exists because the tree is perfect).
3
Descend leftmost
After finishing a level, drop to its leftmost node and repeat until leaves.
04
Solution & live demo
python
▶1class Solution:
▶2 def connect(self, root):
▶3 leftmost = root
▶4 while leftmost and leftmost.left:
▶5 head = leftmost
▶6 while head:
▶7 head.left.next = head.right
▶8 if head.next:
▶9 head.right.next = head.next.left
▶10 head = head.next
▶11 leftmost = leftmost.left
▶12 return root
05
Edge cases
Non-perfect trees (problem 117)
parent.next.left may not exist — needs a scan for the next available child; this version relies on perfection.
Empty tree
Return immediately.
06
Complexity
Time
O(n)
Space
O(1)
Prior level serves as the queue.