Populating Next Right Pointers in Each Node

medium tree dfs bfs linked list

Problem

You are given a perfect binary tree where each node's left and right children are present. Populate each next pointer to point to the node on its immediate right at the same level; if none exists, next should be NULL. Use only constant extra space — recursion via the call stack does not count.

Inputroot = [1,2,3,4,5,6,7]

Output[1,#,2,3,#,4,5,6,7,#]

Level by level, each node's next points to the next node, ending each level with NULL (#).

levels (must be 1, 3, 7, 15… for a perfect tree)

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

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

class Solution {
    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;
    }
}

Node* connect(Node* root) {
    if (!root) return nullptr;
    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;
}

Explanation

This is the perfect tree version: every node has both children, so we can connect each node's next pointer using nothing but a few variables — no queue and no extra memory.

We keep a pointer leftmost that marks the first node of the level we are working on. A second pointer cur sweeps across that level (it can move sideways because that level's next pointers are already set).

At each cur, there are two links to make. First, the two children of the same parent: cur.left.next = cur.right. Second, the gap between two parents: cur.right.next = cur.next.left — that is, my right child points to my right neighbour's left child. The if (cur.next) check skips that second link at the end of a level.

Example with a 3-level tree: at the root we set 2.next = 3. Then we move leftmost down to node 2 and sweep: 4.next = 5 (same parent), then 5.next = 6 (across to node 3's child), then 6.next = 7.

Once a level's links are done, leftmost = leftmost.left drops us to the next level, and we stop when there are no more children. Because the perfect shape guarantees every needed child exists, this constant-space walk wires the whole tree.

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