Populating Next Right Pointers in Each Node

Problem

Populate each node's next pointer to point to its next right node. If no right node, set to NULL.

Key insight (perfect binary tree): Use already-set next pointers on current level to set next level. O(1) space.

Approach — O(1) Space using established next pointers

leftmost = root
while leftmost.left:
    cur = leftmost
    while cur:
        cur.left.next = cur.right
        if cur.next: cur.right.next = cur.next.left
        cur = cur.next
    leftmost = leftmost.left

Solutions

// C (O(1) space, perfect BT)
Node* connect(Node* root) {
    if (!root) return NULL;
    Node* leftmost = root;
    while (leftmost->left) {
        Node* cur = leftmost;
        while (cur) {
            cur->left->next = cur->right;
            if (cur->next) cur->right->next = cur->next->left;
            cur = cur->next;
        }
        leftmost = leftmost->left;
    }
    return root;
}

// C++
Node* connect(Node* root) {
    if (!root) return nullptr;
    auto leftmost = root;
    while (leftmost->left) {
        auto cur = leftmost;
        while (cur) {
            cur->left->next = cur->right;
            if (cur->next) cur->right->next = cur->next->left;
            cur = cur->next;
        }
        leftmost = leftmost->left;
    }
    return root;
}

// Java
public Node connect(Node root) {
    if (root == null) return null;
    Node leftmost = root;
    while (leftmost.left != null) {
        Node cur = leftmost;
        while (cur != null) {
            cur.left.next = cur.right;
            if (cur.next != null) cur.right.next = cur.next.left;
            cur = cur.next;
        }
        leftmost = leftmost.left;
    }
    return root;
}

// JavaScript
function connect(root) {
    if (!root) return null;
    let leftmost = root;
    while (leftmost.left) {
        let cur = leftmost;
        while (cur) {
            cur.left.next = cur.right;
            if (cur.next) cur.right.next = cur.next.left;
            cur = cur.next;
        }
        leftmost = leftmost.left;
    }
    return root;
}

# Python
def connect(root):
    if not root:
        return None
    leftmost = root
    while leftmost.left:
        cur = leftmost
        while cur:
            cur.left.next = cur.right
            if cur.next:
                cur.right.next = cur.next.left
            cur = cur.next
        leftmost = leftmost.left
    return root

Complexity

Time: O(n)
Space: O(1) — leverages already-connected next pointers

Key Insight

Once level L is connected, traverse it using next pointers to connect level L+1.