☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Populating Next Right Pointers in Each Node

Medium TUF ID 823 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a perfect binary tree: every internal node has exactly two children and all leaves are on the same level. Besides left and right, each node has a pointer next, initially null. Set every node’s next to the node immediately to its right on the same level. The rightmost node of each level keeps next == null. Return the root.

Although the SDE sheet lists this problem on its BST day, the tree is not a search tree and values play no role; the problem is about levels.

Constraints (LeetCode 116): 0 to 2^12 - 1 nodes, values in [-1000, 1000]. The follow-up asks for constant extra space. The Java file tests every perfect tree up to depth 17 (131071 nodes).

Example 1

before:            after:
      1                  1 -> null
     / \                / \
    2   3              2 -> 3 -> null
   / \ / \            / \  / \
  4  5 6  7          4->5->6->7 -> null

serialized answer: [1, #, 2, 3, #, 4, 5, 6, 7, #]

The LeetCode serialization reads each level by following next pointers and ends each level with #.

Example 2

root = []           // empty tree
answer = []

There are two different kinds of links to create. Sibling links join two children of the same parent (2 -> 3, 4 -> 5). Cousin links cross a boundary between parents (5 -> 6), and they are the interesting part.

Approach 1: Level order traversal with a queue

Intuition. “Next node on the same level” is precisely the order in which a breadth-first traversal produces a level. Process the tree one level at a time (read the queue size at the start of each round), and link each dequeued node to the one dequeued just before it. The first node of a level has no predecessor, and the last node is never assigned a next, so it stays null.

Algorithm.

  1. If the root is null, return null. Enqueue the root.
  2. While the queue is not empty:
    • Let size be the current queue size and prev = null.
    • Dequeue size nodes. For each, set prev.next = node if prev exists, then prev = node, and enqueue its children.
  3. Return the root.
static Node levelOrder(Node root) {
    if (root == null) return null;
    Deque<Node> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node prev = null;
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            if (prev != null) prev.next = node;          // the last node of the level keeps next == null
            prev = node;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    return root;
}

Complexity. Time O(n), each node enqueued and dequeued once. Space O(n): the last level of a perfect tree holds (n + 1) / 2 nodes, all in the queue at once. This works for any binary tree, not only perfect ones, but it does not meet the follow-up’s constant-space requirement.

Approach 2: Recursion that wires each node’s children

Intuition. Let each node take responsibility for the next pointers of its two children.

Is node.next always ready when we need it? A node’s next is set by its parent, and the parent sets both children’s next pointers before recursing into either child. So by the time connect(child) runs, child.next is final. The root’s next is null, which is already correct. By induction on depth, every call sees a correct next pointer for its own node.

The perfect-tree guarantee is what makes this safe: if a node has a left child it also has a right child, and if node.next exists it also has a left child.

Algorithm.

  1. If the node is null or a leaf (no left child), return.
  2. node.left.next = node.right.
  3. If node.next != null: node.right.next = node.next.left.
  4. Recurse into the left child, then the right child.
static Node recursive(Node root) {
    connect(root);
    return root;
}

static void connect(Node node) {
    if (node == null || node.left == null) return;      // perfect tree: no left child means a leaf
    node.left.next = node.right;                         // siblings
    if (node.next != null) node.right.next = node.next.left;   // cousins across the parent boundary
    connect(node.left);
    connect(node.right);
}

Complexity. Time O(n), constant work per node. Space O(log n) for the recursion, since a perfect tree with n nodes has height log2(n + 1). That is already tiny, but it is not strictly constant.

Approach 3: Optimal, walk each finished level as a linked list

Intuition. Approach 2 never really needed recursion. Once a level is fully linked, it is a linked list: start at its leftmost node and follow next. While walking that list we can do exactly the same two assignments for each node’s children, which links the level below. Then move down to the leftmost node of the next level (leftmost.left) and repeat. The next pointers we just created serve as the “queue” for the following level, so no extra memory is needed.

Algorithm.

  1. leftmost = root.
  2. While leftmost exists and has children:
    • For cur from leftmost along next: set cur.left.next = cur.right, and if cur.next != null, set cur.right.next = cur.next.left.
    • leftmost = leftmost.left.
  3. Return the root.
static Node optimal(Node root) {
    Node leftmost = root;
    while (leftmost != null && leftmost.left != null) {
        for (Node cur = leftmost; cur != null; cur = cur.next) {
            cur.left.next = cur.right;
            if (cur.next != null) cur.right.next = cur.next.left;
        }
        leftmost = leftmost.left;                        // first node of the next level
    }
    return root;
}

Dry run on Example 1:

leftmost cur links created
1 1 2 → 3 (sibling); 1 has no next
2 2 4 → 5 (sibling), 5 → 6 (cousin, via 2.next = 3)
2 3 6 → 7 (sibling); 3 has no next
4   4 is a leaf, stop

Complexity. Time O(n): every internal node is cur exactly once (leaves never are), and each step is constant work. Space O(1): only leftmost and cur.

Edge cases and pitfalls