Populating Next Right Pointers in Each Node II

Difficulty: Medium
Topics: Linked List, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Problem Description

Given a binary tree


struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:


Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:


Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 6000].
-100 <= Node.val <= 100

Follow-up:

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Solution

1. Problem Deconstruction

Technical Restatement
Given a binary tree structure with an additional next pointer per node, implement an algorithm that horizontally connects each node to its immediate right neighbor at the same depth level. The connection must follow level-order sequencing, with terminal nodes pointing to NULL. The solution must handle arbitrary binary tree topologies (not just perfect/complete trees) while optimizing for spatial complexity.

Beginner-Friendly Explanation
Imagine you’re organizing people standing in rows, where each person can see only the person immediately to their right in the same row. Some positions might be empty. Your task is to make sure everyone knows who’s on their right, and if nobody’s there, they should know they’re at the end of the row. The challenge is doing this while using very little extra memory.

Mathematical Formulation
Let:

$L_d = \{n_{d,1}, n_{d,2}, ..., n_{d,k}\}$ represent nodes at depth $d$
$\text{next}(n_{d,i}) = \begin{cases} n_{d,i+1} & \text{if } i < k \\ \text{NULL} & \text{otherwise} \end{cases}$
$\text{parent}(n)$ maps child nodes to their parents
The transformation must satisfy: $\forall d \in \mathbb{Z}^+, \forall i \in [1, |L_d|), \text{next}(n_{d,i}) = n_{d,i+1}$

Constraint Analysis

Node range [0, 6000]: Eliminates O(n²) approaches (>36M operations). Permits O(n) with moderate constant factors.
Value range [-100, 100]: Irrelevant to algorithm design (values unused in logic).
Empty tree (0 nodes): Base case requiring immediate NULL return.
Skewed trees: Worst-case depth = 6000, risking stack overflow for recursive solutions.
Sparse levels: Levels may have discontinuous node distribution, complicating neighbor detection.
Memory constraints: Follow-up demands O(1) extra space excluding stack, invalidating standard BFS queue approaches.

2. Intuition Scaffolding

Real-World Metaphor
Like connecting same-floor apartments in a building with irregular room layouts. You can’t jump between floors - must find adjacent rooms horizontally. The building manager can only remember one floor at a time while installing the intercom system.

Gaming Analogy
In a side-scroller game with platforms at different heights, characters on the same platform need to form chains. You can only walk on platforms you’ve already discovered, using characters on higher platforms as guides to find neighbors.

Math Analogy
Similar to constructing a horizontal linked list for each row of Pascal’s Triangle when the triangle has missing elements. You must propagate connection information downward using only previously established links.

Common Pitfalls

Assuming perfect binary tree: Trying parent→left→right→next shortcuts that fail with missing nodes
Level-order with queue: Violates O(1) space requirement (queue size ≈ n/2)
Right-biased traversal: Missing left subtree connections when right subtree is empty
Depth-first recursion: Losing track of level progression without additional storage
Overwriting next pointers prematurely: Destroying information needed for deeper levels

3. Approach Encyclopedia

Approach 1: Level-Order Traversal with Queue

from collections import deque

def connect_queue(root):
    if not root: return None
    q = deque([root])
    while q:
        level_size = len(q)
        for i in range(level_size):
            node = q.popleft()
            if i < level_size - 1:
                node.next = q[0]  # Peek next node
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
    return root

Complexity Proof

Time: $T(n) = \sum_{d=0}^{h} |L_d| = n$ visits × $O(1)$ operations = $O(n)$
Space: $S(n) = \max(|L_d|) \approx n/2$ in worst-case = $O(n)$

Visualization

Level 0: [1] → NULL
Level 1: [2 → 3] → NULL  
Level 2: [4 → 5 → 7] → NULL
Queue state: [1] → [2,3] → [4,5,7]

Approach 2: Recursive DFS with Level Tracking

def connect_dfs(root):
    levels = {}
    
    def dfs(node, depth):
        if not node: return
        if depth in levels:
            levels[depth].next = node
        levels[depth] = node
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    
    dfs(root, 0)
    return root

Complexity Proof

Time: $T(n) = n$ visits = $O(n)$
Space: $S(n) = O(h)$ recursion stack + $O(h)$ dictionary = $O(h)$ where $h \leq n$

Approach 3: Iterative O(1) Space (Optimal)

def connect_constant(root):
    current = root
    dummy = Node(0)  # Sentinel node
    tail = dummy
    
    while current:
        if current.left:
            tail.next = current.left
            tail = tail.next
        if current.right:
            tail.next = current.right  
            tail = tail.next
        
        current = current.next
        if not current:  # Level finished
            current = dummy.next  # Move to next level
            dummy.next = None  # Reset
            tail = dummy
    
    return root

Complexity Proof

Time: $T(n) = n$ node visits = $O(n)$
Space: $S(n) = 3$ pointers = $O(1)$

Visualization

Level 0: 1 → NULL
         ↓
Level 1: dummy → 2 → 3 → NULL
                 ↓
Level 2: dummy → 4 → 5 → 7 → NULL

4. Code Deep Dive

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

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        # Level 0: Handle empty tree (Example 2)
        if not root:
            return None
            
        current = root  # Tracks current node in current level
        dummy = Node(0)  # Sentinel node for next level's head
        tail = dummy     # Tracks last node in next level
        
        while current:
            # Process current level, building next level
            if current.left:
                tail.next = current.left  # Link new node to chain
                tail = tail.next          # Advance tail pointer
            if current.right:
                tail.next = current.right
                tail = tail.next
                
            # Move to next node in current level
            current = current.next
            
            # Level transition logic
            if not current:
                # Current level exhausted, descend
                current = dummy.next  # Start of next level
                dummy.next = None     # Reset sentinel
                tail = dummy          # Reset tail
                
        return root

Line-by-Line Analysis

Lines 2-3: Handle Example 2’s empty input constraint
Line 5: current traverses nodes horizontally within level
Line 6: dummy provides anchor for next level’s linked list
Line 7: tail always points to last node in next level chain
Lines 10-15: Process both children (handles sparse nodes)
Line 18: Horizontal movement using previously set next pointers
Lines 21-25: Critical level transition - preserves O(1) space

Edge Case Handling

Example 1: Node 5’s right is NULL, but 7 gets connected via node 3
Single node: While loop terminates after level 0
Left-heavy tree: Right pointer NULL handled naturally
Discontinuous levels: Dummy node ensures proper chaining

5. Complexity War Room

Hardware-Aware Analysis

6000 nodes × 4 pointers/node ≈ 24KB tree structure
Algorithm uses 3 pointers ≈ 24 bytes (fits in register)
Memory access pattern: Mostly sequential within levels (cache-friendly)
Worst-case 6000-level skewed tree: ~6000 stack frames (implicit recursion)

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute BFS	O(n)	O(n)	10/10	✅ Good fallback
Recursive DFS	O(n)	O(h)	8/10	✅ Acceptable
Iterative O(1)	O(n)	O(1)	6/10	✅ Optimal
Level Map	O(n)	O(h)	9/10	✅ Clear alternative

6. Pro Mode Extras

Variants & Extensions

Populating Next Right Pointers I (Perfect Binary Tree)

# Simplified - always has both children
while current and current.left:
    next_level = current.left
    while current:
        current.left.next = current.right
        if current.next:
            current.right.next = current.next.left
        current = current.next
    current = next_level

Connect All Nodes in DFS Order

# Transform to singly-linked list in DFS order
prev = None
def dfs(node):
    nonlocal prev
    if not node: return
    if prev: prev.next = node
    prev = node
    dfs(node.left)
    dfs(node.right)

Binary Tree to Linked List (Flatten)

# Different problem - destructive transformation
while current:
    if current.left:
        runner = current.left
        while runner.right: 
            runner = runner.right
        runner.right = current.right
        current.right = current.left
        current.left = None
    current = current.right

Interview Cheat Sheet

First Mention: “I’ll solve this in O(n) time with O(1) space using level-by-level traversal”
Key Insight: “We can use the next pointers we’re creating as a queue for the next level”
Testing Strategy:
1. Empty tree
2. Single node
3. Perfect binary tree
4. Sparse tree (like example)
5. Left/right skewed trees
Common Gotchas:
- “Remember to reset the dummy pointer between levels”
- “Handle both children even if one is NULL”
- “The tail must advance after each connection”

#117 - Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

Problem Description

Solution

1. Problem Deconstruction

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras