Populating Next Right Pointers in Each Node

How it works

Instead of using a queue, we can leverage the next pointers we've already established to traverse each level. We process the tree level by level, using the current level's next pointers to iterate horizontally while setting up the connections for the next level.

Two pointers track our position: one for the current node being processed, and one for the leftmost node of the next level (so we know where to start the next iteration).

Steps

1. Initialize cur to the root and nxt to the root's left child (the start of the next level).
2. While both cur and nxt are not null:
   • Connect cur.left.next to cur.right.
   • If cur.next exists, connect cur.right.next to cur.next.left.
   • Move cur to cur.next.
   • If cur becomes null, move to the next level: set cur to nxt and nxt to cur.left.
3. Return the root.

Complexity

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

Things to watch for

Connecting Nodes Across Different Levels

When iterating through nodes, it is easy to accidentally set the last node of one level to point to the first node of the next level. Always track the level size or use a marker to know when a level ends, ensuring the rightmost node's next stays null.

Missing the Cross-Parent Connection

For a node's right child, its next should be the left child of the node's next neighbor (if it exists). Forgetting this connection leaves gaps in the horizontal links, breaking the chain between subtrees rooted at different parents.

Assuming the Optimal Solution Works for Non-Perfect Trees

The O(1) space solution leveraging the perfect binary tree structure (every node has 0 or 2 children, all leaves at same level) does not generalize. Applying it to arbitrary binary trees produces incorrect results because the assumptions about child existence fail.

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        cur, nxt = root, root.left if root else None

        while cur and nxt:
            cur.left.next = cur.right
            if cur.next:
                cur.right.next = cur.next.left

            cur = cur.next
            if not cur:
                cur = nxt
                nxt = cur.left

        return root

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;

        Node* cur = root, *nxt = root->left;

        while (cur && nxt) {
            cur->left->next = cur->right;
            if (cur->next) {
                cur->right->next = cur->next->left;
            }

            cur = cur->next;
            if (!cur) {
                cur = nxt;
                nxt = cur->left;
            }
        }

        return root;
    }
};