Populating Next Right Pointers in Each Node

Medium Trees & BST Traversals Original on LeetCode

Populating Next Right Pointers in Each Node is a medium trees & bst problem solved with the traversals pattern. The best approach, optimal (walk each level through next pointers), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs with a queue) up.

Problem

You are given a perfect binary tree: every internal node has exactly two children and all leaves sit on the same depth. Each node has the fields val, left, right and an extra pointer next, which starts out as null.

Fill in every next pointer so it points to the node immediately to its right on the same level. The last node of each level keeps next = null. Return the root.

Examples

Example 1

Input
root = [10, 20, 30, 40, 50, 60, 70]
Output
[10, #, 20, 30, #, 40, 50, 60, 70, #]
Why
Each level is read left to right through the next pointers; # marks the end of a level, where next is null.

Example 2

Input
root = [5]
Output
[5, #]
Why
A single node has no right neighbour, so its next stays null.

Example 3

Input
root = []
Output
[]
Why
An empty tree has nothing to connect.

Constraints

  • The tree has 0 to 2^12 - 1 nodes.
  • The tree is perfect: every internal node has two children and all leaves are on the same level.
  • -1000 <= Node.val <= 1000
  • Follow-up: use only O(1) extra space (the recursion stack does not count).

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS with a queue)O(n)O(n)
Optimal (walk each level through next pointers)O(n)O(1)

1Brute force (BFS with a queue)

TimeO(n)Every node is enqueued and dequeued once.
SpaceO(n)The queue holds a whole level, and the last level of a perfect tree has about n / 2 nodes.

Traverse level by level with a queue. Within a level, every node points to the node that comes out of the queue right after it; the last node of the level keeps null.

  1. If root is null, return it.
  2. Push root into a queue.
  3. While the queue is not empty: let size be the current queue size (one level).
  4. Pop size nodes; for each one except the last, set next to the queue's front. Push each node's children.
  5. Return root.
class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node node = q.poll();
                if (i < size - 1) node.next = q.peek();
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
        return root;
    }
}

2Optimal (walk each level through next pointers)

TimeO(n)Each node is visited once as `cur` while its children are linked.
SpaceO(1)Only two pointers; the next links themselves are the output.

The level you are standing on is already linked, so it behaves like a linked list. Walk it with next and wire up the level below: a node's left child points to its right child, and its right child points to the left child of the node's next neighbour. Then drop down to the leftmost node of the next level.

  1. leftmost = root.
  2. While leftmost is not null and has a left child (the level below exists):
  3. Walk cur = leftmost, cur = cur.next: set cur.left.next = cur.right; if cur.next != null, set cur.right.next = cur.next.left.
  4. Move down: leftmost = leftmost.left.
  5. Return root.
class Solution {
    public Node connect(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;
        }
        return root;
    }
}

Edge cases to test

  • Empty tree
  • A single node
  • The rightmost node of every level must keep next = null
  • Linking across subtrees: a left subtree's rightmost node points to the right subtree's leftmost node

Hints

Hint 1

A level-order traversal visits each level left to right, so linking each node to the one dequeued after it (on the same level) works.

Hint 2

Once a level is linked, you can walk it like a linked list using next.

Hint 3

While walking level L, set the children's pointers: node.left.next = node.right, and node.right.next = node.next.left when node.next exists.

FAQ

What is the best time complexity for Populating Next Right Pointers in Each Node?

Optimal (walk each level through next pointers) runs in O(n) time and O(1) extra space. Each node is visited once as `cur` while its children are linked.

Which pattern does Populating Next Right Pointers in Each Node use?

It is a trees & bst problem that uses the traversals pattern. Other problems with the same pattern: Binary Tree Level Order Traversal, Binary Tree Zigzag Level Order Traversal, Binary Tree Level Order Traversal II.

Is there a brute force solution for Populating Next Right Pointers in Each Node?

Yes. Brute force (BFS with a queue) takes O(n) time and O(n) space. Traverse level by level with a queue.

Which edge cases should I test for Populating Next Right Pointers in Each Node?

Empty tree; A single node; The rightmost node of every level must keep next = null; Linking across subtrees: a left subtree's rightmost node points to the right subtree's leftmost node.