The O(n) Club: Populating Next Right Pointers in Each Node II: Now With 100% More Pointer-Juggling

The O(n) Club: Populating Next Right Pointers in Each Node II — Now With 100% More Pointer-Juggling

⚡ TL;DR

Given a binary tree where some nodes have unplanned vacations (read: nulls everywhere), connect each node’s next pointer to its immediate right neighbor at the same level. Forget queues. If you use extra space, the interviewer’s eyebrow goes up. Dummy heads and in-place hacks are your friends.

// O(n) space (bad!):
Queue
<node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
    // not allowed for O(1) space constraints
}</node>

🧠 How Devs Usually Mess This Up

We’ve all confused this with the “perfect” binary tree problem: just wire left to right and stroll home. But sparse trees are wild—the second you try to walk links across missing nodes, your code throws a NullPointer tantrum. And if your first move is to grab a queue, congrats! You just broke the rules and blew O(1) space. Bonus: only connecting siblings on the same parent leaves everyone else ghosted.

🔍 What’s Actually Going On

Picture a busted office floor plan. Some desks are empty. Your job? Pass meeting notes from left to right at each row, skipping the missing chairs, using nothing but sticky-note ingenuity. The trick: each round, you sweep a row while building the next row’s connections with a “dummy” intern carrying the pointer baton. This intern quietly builds the next ‘linked’ level, and you move down once done.

Or, if you prefer coding metaphors: create a dummy node at each level, walk across with a tail pointer, carefully bridging gaps. No lost references, no extra bags.

🛠️ PseudoCode

• Set current to root. While there’s a level to process:
• Create a dummy head node for the next level.
• Start a tail pointer at dummy head.
• While walking the current level:
• If current.left exists, set tail.next = current.left and move tail.
• If current.right exists, tail.next = current.right and move tail.
• Hop to current.next (across the row).
• At the end, current = dummyHead.next to start the next level.

Node current = root;
while (current != null) {
    Node dummy = new Node(0);
    Node tail = dummy;
    while (current != null) {
        if (current.left != null) {
            tail.next = current.left;
            tail = tail.next;
        }
        if (current.right != null) {
            tail.next = current.right;
            tail = tail.next;
        }
        current = current.next;
    }
    current = dummy.next;
}

💻 The Code

// Definition for a Node.
class Node {
    public int val;
    public Node left, right, next;
    public Node(int val) { this.val = val; }
}
 public Node connect(Node root) {
    Node current = root;
    while (current != null) {
        Node dummy = new Node(0);
        Node tail = dummy;
        while (current != null) {
            if (current.left != null) {
                tail.next = current.left;
                tail = tail.next;
            }
            if (current.right != null) {
                tail.next = current.right;
                tail = tail.next;
            }
            current = current.next;
        }
        current = dummy.next;
    }
    return root;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t assume your tree is complete—test with missing children on either side.
• Using a queue or ArrayList? Illegal move for O(1) space (recursion stack doesn’t count, yes that’s weird).
• Check edge cases: empty tree and lone nodes should not break your code.
• Time: O(n), since you must at least look at every poor node.
  Space: O(1) extra, because pointer-juggling takes only skill, not memory.

🧠 Interviewer Brain-Tattoo

Interviewer: “How do you connect next pointers without extra memory?”
You: “I send a dummy intern ahead to make all the links while I stroll rightward—no queues, no drama.”