DSA problem
Populating Next Right Pointers in Each Node II
Given the root of a binary tree (not necessarily perfect, so some nodes may have zero, one, or two children) where each node has an extra next pointer initially set to null, populate every next pointer so that it points to the node immediately to its right on the same level; otherwise leave it as null. Return the root.
This is the harder cousin of the perfect-tree version. We can no longer assume each parent has both children, so the "use cur.next.left to bridge subtrees" trick fails — cur.next.left might be null even though some node further along the level has children. We need a way to find the next non-null child as we sweep across a level.
The trick is a sentinel (dummy) node for the level being built. As we walk across the parent level (using next pointers already populated there), we attach each child we discover to a growing tail that started at the dummy. After the parent-level sweep finishes, the dummy's next points to the leftmost node of the new level, and the chain of next pointers along the new level is automatically complete.
The outer loop runs once per level until the level being built is empty. Inside, two pointers cur (walks the parent level) and tail (grows the child level) drive the work. Total work is O(n); aside from the dummy node, no auxiliary collection is allocated, giving O(1) extra space — the gold standard for this problem.
Examples
root = [1,2,3,4,5,null,7][1,#,2,3,#,4,5,7,#]root = [][]root = [1,2,null,3][1,#,2,#,3,#]Constraints
- The number of nodes in the tree is in the range [0, 6000].
- -100 <= Node.val <= 100
- You may only use constant extra space; the implicit recursion stack does NOT count.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.