Populating Next Right Pointers
mediumTime: O(n)Space: O(1)
Signals to notice
connect each node to next right neighboruse existing next pointersO(1) space level traversal
Brute force first
BFS with queue, connect within each level — O(n) space for queue.
The key insight
Traverse current level via next pointers (already set). Connect children level: left.next = right, right.next = parent.next.left. O(n) time, O(1) space.
What must stay true
The current level's next pointers enable horizontal traversal without a queue. While traversing, connect the next level's children using the parent's next pointer.
Easy way to go wrong
Not connecting across parents — node.right.next should be node.next.left, bridging children of adjacent parents.