Populating Next Right Pointers in Each Node

Given a perfect binary tree, populate each next pointer to point to the next right node. If there is no next right node, the next pointer should be set to NULL.

Example 1

Input: root=[1,2,3,4,5,6,7] → each node's next points to its right neighbor

Solution Approach

Since the tree is perfect, use constant-space level-order using existing next pointers. Process each level by linking children of connected nodes.

Iterate level by level using leftmost node of each level.
For each node at current level: node.left.next = node.right; if node.next: node.right.next = node.next.left.
Advance leftmost to leftmost.left (go to next level).

Java

class Solution {
    public Node connect(Node root) {
        Node leftmost = root;
        while (leftmost != null && 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;
    }
}

Time Complexity: O(N)
Space Complexity: O(1)