Populate Next Right Pointers in Each Node — LC 116 O(1) Space BFS

Problem Statement#

LeetCode 116 — Populate Next Right Pointers in Each Node | Difficulty: Medium

You are given a perfect binary tree where all leaves are on the same level and every parent has two children. Populate each node's next pointer to point to its next right node. If there is no next right node, set it to null. Initially all next pointers are set to null.

Constraints:

• The number of nodes is in the range [0, 2^12 - 1]
• -1000 <= Node.val <= 1000
• The tree is a perfect binary tree

Input:  root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

Input:  root = []
Output: []

Why This Problem Matters#

This problem is a common FAANG interview question that tests whether you can think beyond the obvious BFS-with-queue approach (O(n) space) and find the O(1) space solution. Amazon and Microsoft ask it because it mirrors real-world scenarios where you build linked structures between nodes at the same level — think segment tree lazy propagation, parallel BFS in distributed systems, or level-order processing without a queue.

The O(1) space trick is elegant: once level L is fully connected via next pointers, you can traverse level L using those next pointers to connect level L+1. This bootstraps itself level by level from the root, requiring no auxiliary data structure.

LC 117 (Populate Next Right Pointers II) extends this to arbitrary binary trees — if you master the perfect binary tree case, the general case is a natural extension.

The Core Insight#

For a perfect binary tree, every node has exactly two children. Two types of next connections exist at each level:

1. Same-parent siblings: node.left.next = node.right — always valid for a perfect binary tree.
2. Cross-parent siblings: node.right.next = node.next.left — valid when node.next exists.

Algorithm:

• Start leftmost at the root.
• For each level, traverse it using next pointers (starting from leftmost).
• For each node on the current level, wire up both connection types for its children.
• Advance leftmost to leftmost.left to go to the next level.
• Stop when leftmost.left is null (reached the leaf level).

Visual Dry Run#

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

Level 0 (leftmost = 1):

• Traverse level 0: only node 1
• Wire: 1.left.next = 1.right → 2.next = 3
• No cur.next exists, so no cross-parent connection at this step

Level 1 (leftmost = 2):

• Traverse level 1: node 2, node 3
• At node 2: 2.left.next = 2.right → 4.next = 5; 2.next is 3 → 2.right.next = 2.next.left → 5.next = 6
• At node 3: 3.left.next = 3.right → 6.next = 7; 3.next is null — no cross-parent

Level 2 (leftmost = 4): all leaves, no children to connect.

Solution (Optimal)#

class Solution:
    def connect(self, root):
        if not root:
            return None
 
        leftmost = root  # leftmost node on current level
 
        while leftmost.left:  # stop at leaf level
            cur = leftmost
 
            while cur:  # traverse current level using next pointers
                # Same-parent connection
                cur.left.next = cur.right
 
                # Cross-parent connection (only if cur has a next sibling)
                if cur.next:
                    cur.right.next = cur.next.left
 
                cur = cur.next  # advance along current level
 
            leftmost = leftmost.left  # drop to next level
 
        return root

var connect = function(root) {
    if (!root) return null;
 
    let leftmost = root;
 
    while (leftmost.left) {  // stop at leaf level
        let cur = leftmost;
 
        while (cur) {  // traverse current level
            // Connect children of same parent
            cur.left.next = cur.right;
 
            // Connect right child to left child of next parent
            if (cur.next) {
                cur.right.next = cur.next.left;
            }
 
            cur = cur.next;  // move to next node on this level
        }
 
        leftmost = leftmost.left;  // descend to next level
    }
 
    return root;
};

Time: O(n) — every node visited exactly once Space: O(1) — no queue, no recursion; uses already-set next pointers for traversal

Common Mistakes#

• Using a BFS queue — valid but O(n) space, missing the O(1) insight
• Forgetting the if cur.next guard for cross-parent connections — cur.next.left crashes when cur is the rightmost node on a level
• Advancing leftmost using leftmost.right instead of leftmost.left — always use the leftmost path to track level entry points
• Stopping the outer loop too early or too late — the condition while leftmost.left correctly stops at the leaf level

Interview Tips#

• State the BFS approach first to show you know it, then optimize to O(1) space
• Draw the two types of connections (same-parent and cross-parent) before coding
• Explicitly explain why you traverse using cur.next instead of a queue
• For the follow-up (LC 117 arbitrary trees), mention that you need a dummy head node technique for each level

Follow-up Questions#

• LC 117: What if the tree is not a perfect binary tree? Use a dummy head node for each level; iterate using next pointers and add children as you encounter them.
• Can you solve this recursively? Yes — recurse on the left child after setting both connection types. Recursion is O(log n) space for a balanced tree.
• How would you handle a BFS approach? Group nodes by level using a queue; for each level, set nodes[i].next = nodes[i+1] for all but the last node.
• What changes if nodes can have 0, 1, or 2 children? You need to find the next non-null node on each level rather than assuming cur.next.left always exists.

Key Takeaways#

• The O(1) space trick bootstraps from the current level: use already-set next pointers to traverse and wire the next level
• Two types of connections per node: same-parent (left.next = right) and cross-parent (right.next = next.left)
• The outer loop advances leftmost down the leftmost path; the inner loop sweeps across the level
• Always guard cross-parent connections with if cur.next to handle the rightmost node on each level
• Time is O(n), space is O(1) — significantly better than the O(n) BFS queue approach
• This technique works specifically for perfect binary trees; arbitrary trees require a dummy-head variant (LC 117)
• The same "use one level to build the next" pattern appears in many BFS optimization problems