Wire Each Node's Next Right Pointer

medium tree bfs

Problem

Each node has an extra next field. Set every next to the node immediately to its right on the same level (or null at the right edge). Works for any binary tree, not just perfect ones.

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;
}

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