Skip to main content
CodePeet

Populating Next Right Pointers in Each Node II

Try it yourself
MediumProblemExternal link

Description

Every node of a binary tree has a next pointer as well as its two children, and every next starts out empty. Point each node's next at the node to its right on the same level. The last node of each level keeps an empty next. Return the root.

The tree need not be full: any node can be missing a child. To show the answer, each level is read from its leftmost node along the next pointers, and the levels are listed top down.

Examples

Example 1

Input: root = [1, 2, 3, 4, 5, null, 7]

Output: [[1],[2,3],[4,5,7]]

Explanation: 5 and 7 are cousins: 5's next is 7, across the gap where 3 has no left child.

Example 2

Input: root = []

Output: []

Explanation: An empty tree has no levels.

Example 3

Input: root = [1, 2, 3, 4, null, null, 5]

Output: [[1],[2,3],[4,5]]

Explanation: 2 has only a left child and 3 only a right one, and 4's next is still 5.

Constraints

  • The number of nodes in the tree is in the range [0, 6000].
  • −100 ≤ Node.val ≤ 100
  • Follow-up: use only constant extra space. The recursion stack doesn't count as extra space here.

Editorial

Brute Force

Intuition

The nodes of one level, left to right, are exactly what a level-order walk takes from its queue in one round, if each round takes as many nodes as the queue holds when the round starts. So walk the tree level by level, and within a round point each node at the one taken after it. The last node of the round keeps an empty next.

Step-by-Step Explanation

Let's trace root = [1, 2, 3, 4, 5, null, 7]:

  1. Level 0 is just 1, so it ends the level. Its children, 2, 3, join the queue.
  2. Level 1 is 2, 3. 2's next is 3, and 3 ends the level. Their children, 4, 5, 7, join the queue.
  3. Level 2 is 4, 5, 7. 4's next is 5, 5's next is 7, and 7 ends the level. They have no children, so the queue is empty.

One Level per Round of the Queue — Indigo is the level being linked; each badge shows where a node's next points. Under the tree, the queue.

Algorithm

  1. Put the root in a queue.
  2. While the queue isn't empty: take its size, then take that many nodes, pointing each one before the last at the next one taken, and put their children in the queue.
  3. Return the root.

Code

JavaScript keeps each level in its own array, so no queue has to shift.

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();          // this level's nodes, and only them
            Node* prev = nullptr;
            for (int k = 0; k < size; k++) {
                Node* node = q.front();
                q.pop();
                if (prev) prev->next = node;   // the node before it on this level points to it
                prev = node;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }                             // the level's last node keeps next = nullptr
        }
        return root;
    }
};

from collections import deque


class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        if root is None:
            return root
        queue = deque([root])
        while queue:
            size = len(queue)             # this level's nodes, and only them
            prev = None
            for _ in range(size):
                node = queue.popleft()
                if prev:
                    prev.next = node      # the node before it on this level points to it
                prev = node
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # the level's last node keeps next = None
        return root

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        Deque<Node> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();      // this level's nodes, and only them
            Node prev = null;
            for (int k = 0; k < size; k++) {
                Node node = queue.poll();
                if (prev != null) prev.next = node;   // the node before it on this level points to it
                prev = node;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }                             // the level's last node keeps next = null
        }
        return root;
    }
}

var connect = function(root) {
    if (root === null) return root;
    let level = [root];
    while (level.length) {               // this level's nodes, and only them
        const below = [];
        for (let k = 0; k < level.length; k++) {
            const node = level[k];
            if (k > 0) level[k - 1].next = node;   // the node before it on this level points to it
            if (node.left) below.push(node.left);
            if (node.right) below.push(node.right);
        }                                 // the level's last node keeps next = null
        level = below;
    }
    return root;
};

Complexity Analysis

Time Complexity: O(n)

Each node goes into the queue once and comes out once.

Space Complexity: O(w)

The queue holds up to a whole level, the widest one, w nodes, which is about half the tree when it's complete.

Why This Approach Is Not Efficient

It's fast, but it needs room for a whole level. On the tests' widest tree, a complete tree of 6,000 nodes, the queue held 2,048 nodes at once, and the follow-up asks for constant extra space.

The way out is in what this problem builds. Once a level is linked, it is a list: start at its leftmost node and follow next. Walking that list visits the level's nodes in order, so their children can be linked one after another as they're met, and that links the level below. Nothing needs storing but where the walk is and the last child linked.

Optimal Approach - Walk Each Linked Level

Intuition

The root alone is a linked level. Then, level by level:

  • Walk the linked level from its leftmost node, head, along next.
  • Link each child met, left before right, after the last child linked so far, tail. A dummy node in front of the level below means even its first child is linked the same way.
  • Move down: the dummy's next is the leftmost node of the level below, the next head.

Step-by-Step Explanation

Let's trace root = [1, 2, 3, 4, 5, null, 7]:

  1. On level 0, 1's children 2 and 3 go on the end of the level below, so tail is now 3.
  2. Level 0 is walked. The level below, 2, 3, is linked, and its first node, 2, is where the next walk starts.
  3. On level 1, 2's children 4 and 5 go on the end of the level below, so tail is now 5.
  4. On level 1, 3's child 7 goes on the end of the level below, so tail is now 7.
  5. Level 1 is walked. The level below, 4, 5, 7, is linked, and its first node, 4, is where the next walk starts.
  6. On level 2, 4 has no children; the walk goes on along 4's next pointer.
  7. On level 2, 5 has no children; the walk goes on along 5's next pointer.
  8. On level 2, 7 has no children, and its next is empty, so the walk of level 2 ends.

Walk a Level, Link the One Below — Indigo is the node being walked; green, the tail, the last child linked. Each badge shows where a node's next points. Under the tree, the level below as it's linked.

Algorithm

  1. Set head = root.
  2. While head isn't empty: make a dummy node and set tail to it. For each node from head along next: if it has a left child, set tail.next to it and move tail there; then the same for the right child. Then set head to the dummy's next.
  3. Return the root.

Code

class Solution {
public:
    Node* connect(Node* root) {
        Node* head = root;                // the leftmost node of the level being walked
        while (head != nullptr) {
            Node before(0);               // the level below, linked as it's found; before.next is its first node
            Node* tail = &before;
            for (Node* node = head; node != nullptr; node = node->next) {   // along this level by its next pointers
                if (node->left) { tail->next = node->left; tail = node->left; }
                if (node->right) { tail->next = node->right; tail = node->right; }
            }
            head = before.next;
        }
        return root;
    }
};

class Solution:
    def connect(self, root: Optional[Node]) -> Optional[Node]:
        head = root                       # the leftmost node of the level being walked
        while head:
            before = tail = Node(0)       # the level below, linked as it's found; before.next is its first node
            node = head
            while node:                   # along this level by its next pointers
                for child in (node.left, node.right):
                    if child:
                        tail.next = child
                        tail = child
                node = node.next
            head = before.next
        return root

class Solution {
    public Node connect(Node root) {
        Node head = root;                 // the leftmost node of the level being walked
        while (head != null) {
            Node before = new Node(0);    // the level below, linked as it's found; before.next is its first node
            Node tail = before;
            for (Node node = head; node != null; node = node.next) {   // along this level by its next pointers
                if (node.left != null) { tail.next = node.left; tail = node.left; }
                if (node.right != null) { tail.next = node.right; tail = node.right; }
            }
            head = before.next;
        }
        return root;
    }
}

var connect = function(root) {
    let head = root;                      // the leftmost node of the level being walked
    while (head !== null) {
        const before = new Node(0);       // the level below, linked as it's found; before.next is its first node
        let tail = before;
        for (let node = head; node !== null; node = node.next) {   // along this level by its next pointers
            if (node.left !== null) { tail.next = node.left; tail = node.left; }
            if (node.right !== null) { tail.next = node.right; tail = node.right; }
        }
        head = before.next;
    }
    return root;
};

Complexity Analysis

Time Complexity: O(n)

Each node is linked once as a child and walked once as a parent.

Space Complexity: O(1)

Only head, tail, the walking node and one dummy per level.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code: each level read along the next pointers it set.

Linking only siblings. node.left.next = node.right

On root = [1, 2, 3, 4, 5, null, 7] the levels read [[1],[2,3],[4,5]]; they should read [[1],[2,3],[4,5,7]]. A left child's next is its sibling, but the right child's next is a cousin, under another parent. Linking siblings alone leaves every cousin unlinked: 5's next in the first example is 7, under 3.

Looking only at the next parent. after = node.next.left or node.next.right

On root = [1, 2, 3, 4, 5, 6, 7, 8, null, null, null, null, null, null, 9] the levels read [[1],[2,3],[4,5,6,7],[8]]; they should read [[1],[2,3],[4,5,6,7],[8,9]]. When the next parent along has no children, the cousin is further right still. Looking at node.next's children alone, and not on past parents with none, leaves the link empty.

Linking the whole queue in one run. prev.next = node

On root = [1, 2, 3, 4, 5, null, 7] the levels read [[1,2],[2,3,4],[4,5,7]]; they should read [[1],[2,3],[4,5,7]]. A breadth-first queue holds the levels one after another, so linking each node to the next one in the queue runs the last node of a level on into the first of the next. Each level has to end in None: take the level's size before linking it.

Where This Pattern Is Taught

This problem practises level-order walking. It's taught in Tree Traversals: Depth-First and Breadth-First, which links the levels this same way, with no queue.