117 - Populating Next Right Pointers in Each Node II

Difficulty: Medium | Pattern: BFS Level Order / Linked-List Traversal | Company tags: Microsoft, Amazon, Facebook

Problem Statement

Given a binary tree, populate each node's next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Use only constant extra space (the next pointers already in the tree count as O(1)).

Note: This problem differs from LC 116 in that the tree is NOT necessarily a perfect binary tree.

Example:

Input: root = [1,2,3,4,5,null,7]
Output: next pointers set so level order = [1,#],[2,3,#],[4,5,7,#]

Approach: BFS Level Order — O(n), O(w) space

from collections import deque

def connect(root):
    if not root:
        return root
    
    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)
    
    return root

Algorithm Flow

O(1) Space: Use Already-Set Next Pointers

Key insight: Once we've connected level i, we can traverse it like a linked list to connect level i+1. Use a "dummy" head and a cursor to build the next level.

def connect(root):
    curr = root
    while curr:
        dummy = type('', (), {'next': None})()  # dummy head for next level
        tail = dummy
        
        while curr:
            for child in [curr.left, curr.right]:
                if child:
                    tail.next = child
                    tail = tail.next
            curr = curr.next
        
        curr = dummy.next
    
    return root

Dry Run

Tree: [1,2,3,4,5,null,7]

Level 1 (root=1): only node 1, set next=None Level 2 (from level 1's next-chain): 2→3→None

• Process 2: children 4,5 → tail chain: 4→5
• Process 3: children null,7 → tail chain: 4→5→7

Level 2 fully connected: 2→3→None; Level 3: 4→5→7→None ✓

Complexity

Approach	Time	Space
BFS	O(n)	O(w) — max level width
O(1) space	O(n)	O(1)

Key Terms

Term	Definition
Level-order traversal	Visiting a tree level by level, typically via BFS with a queue.
Dummy node	A sentinel placeholder used to simplify linked-list-building logic by avoiding null-head edge cases.
Next pointer	An extra pointer field on each node linking it to its right sibling at the same level.
Constant extra space	Using only O(1) auxiliary memory (excluding the pointers already part of the output).

FAQ

Q: Why can we get O(1) space here (unlike a typical BFS)? A: Once level i is connected via next pointers, we can traverse it like a linked list instead of needing a queue, letting us build level i+1's links using only a couple of pointer variables.

Q: Why is this harder than LeetCode 116 (perfect binary tree)? A: In a perfect tree you can assume every node has two children, letting you use direct child-index arithmetic. Here, missing children mean you must dynamically skip gaps while building the next level's chain.

Q: What does the dummy head protect against? A: It avoids special-casing "is this the first child found at the next level" — you always attach to tail.next and start from dummy.next when done.

Q: What breaks if you forget to save curr.next before rewiring? A: You wouldn't — this solution reads curr.left/curr.right (not curr.next) before moving curr = curr.next, so pointers are safe by construction; the risk instead is moving curr before fully processing its children.

Q: How would this differ for a general (non-binary) tree? A: You'd iterate over a variable-length children list per node instead of just left/right, but the level-by-level dummy-chain technique still applies.

Quick Revision

• Two approaches: BFS with a queue (O(w) space) or a pointer-based level walk (O(1) space).
• O(1) approach: use curr.next links of the current level to build the next level's chain.
• Dummy + tail pattern avoids special-casing the first node of each new level.
• After finishing level i, move curr = dummy.next to begin level i+1.
• No assumption of a perfect binary tree — must skip missing children.
• Time O(n) either way; space is O(w) for BFS vs O(1) for pointer-rewiring.
• Process left then right child order to preserve left-to-right ordering.

Related Problems

• 102 - Binary Tree Level Order Traversal — same level-by-level pattern using BFS.
• 199 - Binary Tree Right Side View — another level-order variant, picking the last node per level.