The O(n) Club: Populating Next Right Pointers With Minimal Drama

The O(n) Club: Populating Next Right Pointers With Minimal Drama

⚡ TL;DR

This classic LeetCode problem wants you to connect each tree node to its immediate neighbor. Brute force with a queue works fine—if you enjoy extra memory usage and glaring at your interviewer. The real flex? Make the tree link itself with just next pointers. Java brute force:

// Brute-force BFS with a queue
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
    int size = q.size();
    Node prev = null;
    for (int i = 0; i < size; i++) {
        Node curr = q.poll();
        if (prev != null) prev.next = curr;
        if (curr.left != null) q.offer(curr.left);
        if (curr.right != null) q.offer(curr.right);
        prev = curr;
    }
}

🧠 How Devs Usually Mess This Up

Queue abuse! First instinct: BFS, throw everything in a queue, and stitch nodes as you pop. Too bad the follow-up wants constant space, and queuing up hundreds of nodes isn’t exactly tiny-footprint. Other classic mistake: assuming every tree is a perfect binary snowflake (spoiler: 117 isn’t), so your tidy left-right.next logic explodes when there’s a missing child. Welcome to NullPointerException City—population: you.

🔍 What’s Actually Going On

Think of a tree as a high-rise, and every node wants to gossip with its right-hand neighbor. When the building’s perfect (116), easy—just pass the message along. But throw in random supply closet gaps (117), and you need real logic. The trick: while walking one floor (level), use those existing next pointers like fancy conveyor belts, and, as you go, solder together the pointers for the next floor using a dummy node. When the dust settles, hop down a level and repeat. No queue, no existential crisis.

🛠️ PseudoCode

• Start with levelStart = root.
• For each level:
• Create a dummy node—your faux-root for the coming level.
• Walk current level left-to-right with curr = levelStart, using curr.next.
• If curr.left exists: prev.next = curr.left; set prev = prev.next.
• If curr.right exists: prev.next = curr.right; update prev = prev.next.
• Advance curr = curr.next each time.
• Move levelStart = dummy.next and do it all again. Bail out if levelStart == null.

// Pseudocode in Java style
Node levelStart = root;
while (levelStart != null) {
  Node dummy = new Node(0);
  Node prev = dummy;
  for (Node curr = levelStart; curr != null; curr = curr.next) {
    if (curr.left != null) {
      prev.next = curr.left;
      prev = prev.next;
    }
    if (curr.right != null) {
      prev.next = curr.right;
      prev = prev.next;
    }
  }
  levelStart = dummy.next;
}

💻 The Code

// Java for LeetCode 117: Arbitrary Binary Tree
class Node {
    int val;
    Node left, right, next;
    Node(int val) { this.val = val; }
}
Node connect(Node root) {
    Node levelStart = root;
    while (levelStart != null) {
        Node dummy = new Node(0);
        Node prev = dummy;
        for (Node curr = levelStart; curr != null; curr = curr.next) {
            if (curr.left != null) {
                prev.next = curr.left;
                prev = prev.next;
            }
            if (curr.right != null) {
                prev.next = curr.right;
                prev = prev.next;
            }
        }
        levelStart = dummy.next;
    }
    return root;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Assume missing children! No, really: plenty of nodes will have null kids.
• The last node’s next is always null—rest easy, this scheme handles it for you.
• BFS (with a queue) gets you working code but fails the constant-space litmus test.
• Time: O(n)—thanks, Captain Obvious. Space: O(1) (non-queue edition).

🧠 Interviewer Brain-Tattoo

“Why bring extra bags when the tree’s already packed with pointers? Next time, let the structure do the heavy lifting.”