116. Populating Next Right Pointers in Each Node
You are handed the root of a perfect binary tree — every internal node has exactly two children and all leaves sit on the same bottom level. Besides left and right, each node carries one extra pointer named next, and every next starts out empty.
Wire the tree so that each node's next points to the node immediately to its right on the same level. The last node of every level keeps next = None. Return the root once all the pointers are in place.
A queue gets you there quickly — but since the tree is perfect, can you finish the job with constant extra space?
Example 1:
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1, #, 2, 3, #, 4, 5, 6, 7, #]
Explanation: After wiring, the middle level reads 2 → 3 → None and the leaf level reads 4 → 5 → 6 → 7 → None. Each # marks where a next pointer is None, i.e. the end of a level.
Example 2:
Input: root = [1]
Output: [1, #]
Explanation: A single node is its own level; its next stays None.
Constraints:
- The tree is perfect: every internal node has two children and all leaves share one level.
- 1 ≤ number of nodes ≤ 4095 (at most 12 levels)
- -1000 ≤ Node.val ≤ 1000
Hints:
A breadth-first queue hands you every level in left-to-right order. While draining one level, remember the previously dequeued node and point its next at the current one.
Once a level is fully wired, its next pointers already form a linked list. Walk that list to wire the level below without any queue: parent.left.next = parent.right, and parent.right.next = parent.next.left when parent.next exists.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, 5, 6, 7]
Expected output: [1, #, 2, 3, #, 4, 5, 6, 7, #]