Populating Next Right Pointers in Each Node II

medium tree bfs

Problem

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.

Walk level by level. Use a "head" pointer to enter the next level, and a moving "prev" pointer that strings each new child onto the previous one. Because the current level is already linked, you can sweep it with a simple cur = cur.next walk — no queue needed.

Inputlevel-order: [1, 2, 3, 4, 5, _, 7]

Output1 → null · 2 → 3 → null · 4 → 5 → 7 → null

level-order ('_' for null)

def connect(root):
    cur = root
    while cur:
        dummy = Node(0); prev = dummy
        while cur:
            if cur.left:  prev.next = cur.left;  prev = prev.next
            if cur.right: prev.next = cur.right; prev = prev.next
            cur = cur.next
        cur = dummy.next
    return root

function connect(root) {
  let cur = root;
  while (cur) {
    const dummy = { next: null };
    let prev = dummy;
    while (cur) {
      if (cur.left)  { prev.next = cur.left;  prev = prev.next; }
      if (cur.right) { prev.next = cur.right; prev = prev.next; }
      cur = cur.next;
    }
    cur = dummy.next;
  }
  return root;
}

class Solution {
    public Node connect(Node root) {
        Node cur = root;
        while (cur != null) {
            Node dummy = new Node(0);
            Node prev = dummy;
            while (cur != null) {
                if (cur.left != null)  { prev.next = cur.left;  prev = prev.next; }
                if (cur.right != null) { prev.next = cur.right; prev = prev.next; }
                cur = cur.next;
            }
            cur = dummy.next;
        }
        return root;
    }
}

Node* connect(Node* root) {
    Node* cur = root;
    while (cur) {
        Node dummy(0);
        Node* prev = &dummy;
        while (cur) {
            if (cur->left)  { prev->next = cur->left;  prev = prev->next; }
            if (cur->right) { prev->next = cur->right; prev = prev->next; }
            cur = cur->next;
        }
        cur = dummy.next;
    }
    return root;
}

Explanation

The job is to connect every node to the one on its immediate right on the same level. The clever part is that once a level is fully wired, you can sweep across it for free using the next pointers you already set — so you never need a queue.

The outer loop holds cur, which walks across the current level. While building the next level down, we use a dummy head node and a moving prev pointer. For each node cur, we hook its left then right children onto prev.next, advancing prev each time. This strings all the children of one level into a chain.

When the sweep of the current level finishes, dummy.next points to the first node of the newly-built level, so we set cur = dummy.next and repeat one level lower.

Example: level [2, 3]. We start a fresh dummy. From node 2 we attach 4 then 5; from node 3 we attach 7. Now the chain is 4 → 5 → 7 → null, and dummy.next is 4, which becomes the next cur.

Because each node is touched a constant number of times and the dummy trick avoids tracking the head by hand, the whole thing runs in linear time using only a couple of pointers.

Time: O(n) Space: O(1)