Populating Next Right Pointers in Each Node

Master this topic with zero to advance depth.

Populating Next Right Pointers in Each Node

Connect levels.

Medium

Approach 1

Level I: BFS (Level Order)

Intuition

Standard level-order traversal (BFS) using a queue allows us to process nodes level by level. At each level, we iterate through the nodes and set the next pointer of the current node to the next node in the queue (if it's not the last node of the level).

Thought Process

Standard BFS with Queue.
At each level i (of size S):
For j from 0 to S-1:
- node.next = queue.peek() (if j < S-1).

⏱ O(N)💾 O(N) (Queue stores max level width)

Detailed Dry Run

Level	Node	Queue After Pop	Next Pointer
1	2	[3]	3
1	3	[]	null
2	4	[5, 6, 7]	5

java

public class Main {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                if (i < size - 1) cur.next = queue.peek();
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
        }
        return root;
    }
}

Approach 2

Level II: Recursive DFS

Intuition

We can use the fact that the tree is a perfect binary tree to recursively connect nodes. For any node, we connect its left child to its right child. Then, if the node has a next element, we connect its right child to the next element's left child.

Logic

Base case: if (!root || !root.left) return.
root.left.next = root.right.
if (root.next) root.right.next = root.next.left.
Recurse left and right.

⏱ O(N)💾 O(H)

Detailed Dry Run

root=1: 2.next=3. root=2: 4.next=5, 5.next=6 (if 2.next exists).

java

public class Main {
    public Node connect(Node root) {
        if (root == null || root.left == null) return root;
        root.left.next = root.right;
        if (root.next != null) root.right.next = root.next.left;
        connect(root.left);
        connect(root.right);
        return root;
    }
}

Approach 3

Level III: Optimal (Iterative using Pointers)

Intuition

Thought Process

Since the tree is a perfect binary tree, we can use the already connected next pointers from the current level to connect the children of the next level. This avoids the use of a queue, making it $O(1)$ space.

Logic

Start at the leftmost node of the current level (leftmost).
Iterate through nodes at this level using cur = cur.next.
Connect cur.left.next = cur.right.
Connect cur.right.next = cur.next.left (if cur.next exists).

Complexity

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

⏱ O(N)💾 O(1)

Detailed Dry Run

Level Head	Current	cur.left.next	cur.right.next	Action
1	1	2->3	null	Done with L1
2	2	4->5	5->6	Move to cur=3
2	3	6->7	null	Done with L2

java

public class Main {
    public Node connect(Node root) {
        if (root == null) return null;
        Node leftmost = root;
        while (leftmost.left != null) {
            Node head = leftmost;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null) head.right.next = head.next.left;
                head = head.next;
            }
            leftmost = leftmost.left;
        }
        return root;
    }
}

⚠️ Common Pitfalls & Tips

This $O(1)$ space trick only works for Perfect Binary Trees. For general trees, you need a dummy node and a pointer to track the next level's current node.

← Previous QuestionKth Smallest Element in a BST

Next Question →Serialize and Deserialize Binary Tree

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.