Populating Next Right Pointers in Each Node II

Solving tips

Key insight for O(1) space: once level L's next pointers are wired, level L IS a linked list, so walking it visits level L+1's children left-to-right without a queue.
Use a dummy head and a tail pointer for the level being built: walk parents via next, and for each existing child do tail.next = child; tail = child; then level_head = dummy.next. O(n) time, O(1) space.
A BFS with a queue is the easy O(n)-time baseline but uses O(w) space and ignores the follow-up.
Pitfall: advance across the level with node = node.next (not node.left), don't assume version I's perfect-tree shortcut (missing children break it), and the rightmost node's next stays None.

Problem

You are given a binary tree whose nodes carry an extra pointer field next, initially None everywhere. Wire up every next pointer to point at the node immediately to its right on the same level; the rightmost node of each level keeps next = None. Return the root. Unlike the easier version I of this problem, the tree is not perfect — nodes may be missing anywhere, so a node’s next-right neighbor might live under a distant cousin.

The follow-up that makes this interesting: do it with O(1) extra space (recursion stack not counted as free — the intended answer uses no queue and no recursion proportional to n).

Examples

Input: root = [1,2,3,4,5,null,7] → Output: [1,#,2,3,#,4,5,7,#] Level by level (# ends a level): 1; 2 → 3; 4 → 5 → 7. Note 5.next is 7, a cousin under 3, not a sibling.
Input: root = [2,1,3] → Output: [2,#,1,3,#] 1.next = 3; both 2 and 3 end their levels with None.
Input: root = [] → Output: [] Empty tree — nothing to wire.

Constraints

0 <= n <= 6000 nodes; -100 <= Node.val <= 100.
Any shape allowed — gaps between subtrees are the whole difficulty.
Target: O(n) time; the follow-up asks for O(1) auxiliary space.

Think about it first

Hint 1

A BFS that processes one level per queue drain sees each level's nodes left to right — linking consecutive dequeued nodes is almost free.

Hint 2

Once level L's `next` pointers are wired, level L is itself a linked list. Can you walk that list to visit level L+1's nodes in left-to-right order without a queue?

Hint 3

Use a dummy head and a `tail` pointer for the level being built: walk the current level via `next`, and for each existing child do `tail.next = child; tail = child`. When the walk ends, `dummy.next` is the start of the next level. That's the O(1)-space answer.

TL;DR

Treat each wired level as a linked list to build the next one — O(n) time, O(1) space.

Approach 1 — BFS with a queue (the natural first answer)

Level-order traversal hands us each level’s nodes in left-to-right order, so we can link each dequeued node to the one dequeued after it within the same level. This is the honest baseline rather than a true brute force — there is no meaningfully dumber way to see levels.

# Definition for a Node.
# class Node:
#     def __init__(self, val: int = 0, left: 'Node' = None,
#                  right: 'Node' = None, next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next

from collections import deque

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None
        queue = deque([root])
        while queue:
            prev = None
            for _ in range(len(queue)):
                node = queue.popleft()
                if prev:
                    prev.next = node
                prev = node
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # prev is the level's last node; its next stays None
        return root

Complexity: O(n) time, O(w) space for the queue — up to O(n) on a bushy tree. Correct and constraint-proof, but it ignores the follow-up: the queue stores exactly the information the next pointers themselves could provide.

Approach 2 — Use the previous level as a linked list (O(1) space, the classic)

The insight: after processing level L, its next pointers make level L a singly linked list. Walking that list visits level L’s nodes left to right — and therefore visits level L+1’s children left to right. So we never need a queue: stitch the children together as we walk the parents, using a dummy head so we don’t special-case “first child seen on this level”. This is the same dummy-node technique used everywhere in linked-list problems.

# Definition for a Node.
# class Node:
#     def __init__(self, val: int = 0, left: 'Node' = None,
#                  right: 'Node' = None, next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        level_head = root
        while level_head:
            dummy = Node(0)
            tail = dummy
            node = level_head
            while node:                 # walk the current, already-wired level
                if node.left:
                    tail.next = node.left
                    tail = tail.next
                if node.right:
                    tail.next = node.right
                    tail = tail.next
                node = node.next
            level_head = dummy.next     # first node of the level just built
        return root

Walkthrough on root = [1,2,3,4,5,null,7]:

Level 1: walk node 1. Children: 2 (tail: dummy→2), 3 (2→3). Next level head = 2. Level 2 is now the list 2 → 3.
Level 2 → 3: at 2, children 4 (dummy→4) and 5 (4→5); follow 2.next to 3; 3.left is missing, 3.right = 7 gives 5 → 7. Next level head = 4. Level 3 is 4 → 5 → 7 — the cousin link 5 → 7 happened with no special casing because tail persists across parents.
Level 4 → 5 → 7: no children; dummy.next stays None → loop ends.

Complexity: O(n) time (each node visited once as a parent, once as a child), O(1) extra space — just dummy, tail, and two cursors. (One fresh dummy node per level is O(1) live at a time; you can also hoist a single dummy out of the loop and reset dummy.next = None each level.)

Approach 3 — Recursive next-pointer weaving (worth knowing, with a caveat)

The insight: you can also fix pointers top-down: for each node, find its children’s successors by scanning node.next, node.next.next, ... for the first child on that level. The caveat that makes this one subtle: you must process the right subtree before the left, because finding a left subtree’s successors depends on next pointers already existing to the right.

# Definition for a Node.
# class Node:
#     def __init__(self, val: int = 0, left: 'Node' = None,
#                  right: 'Node' = None, next: 'Node' = None):
#         self.val = val
#         self.left = left
#         self.right = right
#         self.next = next

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None

        def first_child_after(node: 'Optional[Node]') -> 'Optional[Node]':
            while node:
                if node.left:
                    return node.left
                if node.right:
                    return node.right
                node = node.next
            return None

        if root.left:
            root.left.next = root.right or first_child_after(root.next)
        if root.right:
            root.right.next = first_child_after(root.next)
        self.connect(root.right)   # right first — see insight above
        self.connect(root.left)
        return root

Walkthrough on [1,2,3,4,5,null,7]: at 1, set 2.next = 3 and 3.next = None. Recurse right into 3: 7.next = None (no node after 3). Recurse left into 2: 4.next = 5; for 5.next, scan 2.next = 3 → first child is 7 → 5.next = 7. Same wiring as Approach 2.

Complexity: O(n) time amortized (each next chain hop corresponds to a gap that is scanned O(1) times overall per level)… but worst case a level scan can be O(w), giving O(n) total per level chain and O(n) overall — still linear. Space is O(h) recursion stack, so it does not meet the strict O(1) follow-up; it’s shown because interviewers frequently probe the right-before-left ordering trap.

Common pitfalls

Forgetting the level’s last node must keep next = None — with the dummy technique it’s automatic; with manual prev linking it’s easy to leave a stale pointer.
In the O(1) approach, advancing with node = node.left instead of node = node.next — the walk moves across the wired level, not down.
In the recursive version, recursing left before right: the left subtree then scans next chains that haven’t been built yet and misses cousins.
Assuming version I’s perfect-tree shortcut (node.left.next = node.right; node.right.next = node.next.left) still works — missing children break it.

Pattern takeaway

Pointers you’ve already installed are free data structure. Once a level is wired, it is the queue for the next level — a recurring trick: when an algorithm builds connectivity as it goes (next pointers, parent links, threaded trees like Morris traversal), check whether the structure built so far can replace the auxiliary container you were about to allocate.