Populating Next Right Pointers in Each Node II

Problem

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

Follow-up: solve it using O(1) extra space. The recursion stack does not count as free, so 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 tree shape is allowed; gaps between subtrees are the main difficulty.
• Target: O(n) time; the follow-up asks for O(1) auxiliary space.

Think about it first

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 visits 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 baseline solution; it uses a queue but ignores the follow-up.

# 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

def connect(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 wide tree. It is correct and within constraints, but it ignores the follow-up: the queue stores exactly the information the next pointers already provide.

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

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 do not need a queue: link the children together as we walk the parents, using a dummy head to avoid a special case for the first child on the level. This is the standard dummy-node technique from 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

def connect(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

The tree root = [1,2,3,4,5,null,7] with solid tree edges and dashed next pointers:

flowchart TD
  n1[1] --> n2[2]
  n1 --> n3[3]
  n2 --> n4[4]
  n2 --> n5[5]
  n3 --> n7[7]
  n2 -.next.-> n3
  n4 -.next.-> n5
  n5 -.next.-> n7

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)

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 subtle part is ordering: 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

def connect(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)
    connect(root.right)   # right first — see insight above
    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. Each next-chain scan is bounded by the level width, and the scans across a level sum to O(w), giving O(n) overall. Space is O(h) for the recursion stack, so this does not meet the strict O(1) follow-up. It is worth knowing because interviewers often probe the right-before-left ordering requirement.

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 have already set can serve as a data structure. Once a level is wired, it acts as the queue for the next level. 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.