DSA problem
Populating Next Right Pointers in Each Node
You are given a perfect binary tree where every parent has two children and all leaves are on the same level. Each node has an extra next pointer that initially points to null. Populate every next pointer so that it points to the node immediately to its right on the same level; if there is no such node, leave it as null. The function should return the root of the modified tree.
A straightforward BFS solution would queue the nodes level by level and stitch each level into a linked list. That works in O(n) time but uses O(n / 2) = O(n) extra space at the widest level, which violates the spirit of the problem's "constant extra space" follow-up.
The optimal approach exploits the perfect-tree invariant. Once a level has been fully wired with next pointers, we can sweep across that level using those pointers as a temporary linked list, and from each node on the current level we can connect its two children (left.next = right) AND connect that right child to the next subtree's left child via cur.next.left — guaranteed non-null because the tree is perfect. This makes the algorithm run in O(n) time with strictly O(1) extra space (ignoring the implicit recursion stack we are explicitly NOT using here).
The classical pattern is two nested loops: an outer loop that advances leftmost from one level's first node to the next level's first node, and an inner loop that uses already-established next pointers to walk across the current level wiring up the children below.
Examples
root = [1,2,3,4,5,6,7][1,#,2,3,#,4,5,6,7,#]root = [][]root = [1,2,3][1,#,2,3,#]Constraints
- The number of nodes in the tree is in the range [0, 2^12 - 1].
- -1000 <= Node.val <= 1000
- The given tree is a perfect binary tree.
- You may only use constant extra space; the recursion stack used by a recursive approach does NOT count as extra space.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.