Populating Next Right Pointers
mediumTime: O(n)Space: O(1)
Recognize the pattern
connect each node to next right neighboruse existing next pointersO(1) space level traversal
Brute force idea
BFS with queue, connect within each level — O(n) space for queue.
Better approach
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.
Key invariant
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.
Watch out for
Not connecting across parents — node.right.next should be node.next.left, bridging children of adjacent parents.