What is the brute force approach and complexity for Populating Next Right Pointers in Each Node?

BFS with a queue; link each popped node to the front of the queue unless it is the last of its round with time complexity O(N) and space complexity O(W).

What is the optimal approach and complexity for Populating Next Right Pointers in Each Node?

Start at the leftmost node; for each node on a row, link its children, plus one cross link to the next parent's left child with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Populating Next Right Pointers in Each Node?

Look for key signals in the prompt: "connect each node to its right neighbour" indicates Each row is a list of nodes. The row above can supply that list through its next pointers.; "perfect binary tree" indicates Every row is full, so each node above the leaves has exactly two children. That lets the walk use cur->left without a null check.; "constant extra space follow-up" indicates No queue. The next pointers we are setting become the queue..

Populating Next Right Pointers in Each Node

Medium·LeetCode #116Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree next pointers: level walk with the level above as a linked list

Complexity:O(N)→O(N)

Key Insight

Use the next pointers of the row above as the queue. Start at the root. For each row, walk it with next and link the children of each node. Between two neighbouring parents, add one cross link from the right child to the next parent's left child. Then move down to the leftmost node of the row below.

Core Validity Invariant

Children of neighbouring nodes are neighbours too, so walking one row with next links the whole row below it.

Problem

You are given a perfect binary tree: every parent has exactly two children, and all leaves are on the same level. Each node has a next pointer, and all of them start as null.

Set every next pointer to the node on its right, on the same level. If there is no node on the right, set it to null. Return the root.

Input

The root of a perfect binary tree (it can be empty). Each node has val, left, right and next.

Output

The same root, with every next pointer filled in.

Example 1

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

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

The output lists the nodes level by level, following the next pointers. # marks the end of each level. Node 5 points to node 6, even though their parents (2 and 3) are different.

Example 2

Input: root = []

Output: []

An empty tree has no nodes, so there is nothing to set.

Constraints

• The number of nodes is in the range [0, 2^12 − 1]
• −1000 ≤ Node.val ≤ 1000
• Follow-up: can you use only constant extra space?

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
What is a next pointer here? Which nodes are on the same level?
2.
Can a node's next be a node with a different parent? Find one example in the tree above.
3.
The tree is perfect. What does that tell me about how many nodes each level has?
4.
A queue of one level gives me the nodes in order. How much extra space does it take, and can I avoid it?
5.
Once a level is linked by next, can I use those links to walk that level and link the one below?

Brute force approach

Idea

Process the tree level by level with a queue. Each round pops exactly the nodes of one level. Link each popped node to the next node popped in the same round. The last node of each round has no next, so it stays null.

Thinking process

1
A level in a perfect tree is one round of level order. The queue holds the nodes of one level, and they come out left to right.
2
After popping a node, the front of the queue is the next node on the same level, unless this was the last node of the round. On [1, 2, 3, 4, 5, 6, 7]: round 2 pops 2 and the front is 3, so 2.next = 3. Then it pops 3, the last of the round, so 3.next stays null.
3
Round 3 pops 4, 5, 6 and 7 and links 4 → 5 → 6 → 7. Node 5 gets 6 as its next, even though their parents differ.
4
The round size is the boundary. Pop exactly that many nodes per round, so the links never cross into the next level.

Visual

Circles are tree nodes; dashed arrows are next pointers. The queue (front on the left) holds the nodes of the current level and the next. Blue = in the queue, green = popped. The last node popped in a round gets no next.

BFS queue links each levelroot = [1, 2, 3, 4, 5, 6, 7] (perfect binary tree)step 1/12

queue

▲front

Popped so far (in order)

[ ]

Start: the queue holds the root

A level order queue. Each round pops exactly the nodes of one level.

Code & Implementation

brute.cpp

// class Node { int val; Node *left; Node *right; Node *next; };  (given by LeetCode)
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;

        // Level order: the queue holds one whole level, then the next one.
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();                  // nodes on this level
            for (int i = 0; i < size; i++) {
                Node* cur = q.front();
                q.pop();
                // After popping cur, the front of the queue is the next node on this level.
                // The last node of the level has no next node, so its next stays null.
                if (i + 1 < size) cur->next = q.front();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }
        return root;
    }
};

import java.util.*;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    public Node(int _val) { val = _val; }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val; left = _left; right = _right; next = _next;
    }
}

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;

        // Level order: the queue holds one whole level, then the next one.
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();                  // nodes on this level
            for (int i = 0; i < size; i++) {
                Node cur = q.poll();
                // After popping cur, the front of the queue is the next node on this level.
                // The last node of the level has no next node, so its next stays null.
                if (i + 1 < size) cur.next = q.peek();
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }
        return root;
    }
}

from typing import Optional
from collections import deque

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: Optional['Node']) -> Optional['Node']:
        if not root:
            return None

        # Level order: the queue holds one whole level, then the next one.
        q: deque[Node] = deque([root])
        while q:
            size = len(q)                  # nodes on this level
            for i in range(size):
                cur = q.popleft()
                # After popping cur, the front of the queue is the next node on this level.
                # The last node of the level has no next node, so its next stays null.
                if i + 1 < size:
                    cur.next = q[0]
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        return root

export class _Node {
    val: number;
    left: _Node | null;
    right: _Node | null;
    next: _Node | null;
    constructor(val?: number, left?: _Node | null, right?: _Node | null, next?: _Node | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
        this.next = (next === undefined ? null : next);
    }
}
export { _Node as Node };

export function connect(root: _Node | null): _Node | null {
    if (!root) return null;

    // Level order: the queue holds one whole level, then the next one.
    const q: _Node[] = [root];
    while (q.length > 0) {
        const size = q.length;                  // nodes on this level
        for (let i = 0; i < size; i++) {
            const cur = q.shift()!;
            // After popping cur, the front of the queue is the next node on this level.
            // The last node of the level has no next node, so its next stays null.
            if (i + 1 < size) cur.next = q[0];
            if (cur.left) q.push(cur.left);
            if (cur.right) q.push(cur.right);
        }
    }
    return root;
}

Complexity

Time O(N)Space O(W)

Every node is pushed and popped once, so the time is O(N). The queue holds at most one level at a time, so the extra space is O(W), the widest level (up to about N/2 nodes in a perfect tree). The optimal does the same links with O(1) extra space: it uses the next pointers that are already set on the row above as its queue.

Optimized approach

Idea

Start from brute force

The brute queue stores a whole level just to know which node comes next. But once the row above is linked, that order is already stored in the next pointers.

Find the repeated work

The queue rediscovers the order of each row from scratch, and it holds that order in extra memory. In a perfect tree, the children of one row form the next row in order, so the next pointers of the row above give the order for free.

Define the state — what variables do I need?

leftmost: The first node of the row being linked. Its left child is the first node of the row below. It moves down one row per loop.
cur: The node on the current row whose children are being linked. It walks the row with next.

Define validity

Children of neighbouring nodes are neighbours too, so walking one row with next links the whole row below it.

Define the transitions — when does each pointer move, and why is it safe?

Start of a row

cur = leftmost

The first node of the row is where the walk starts.

For each cur

cur->left->next = cur->right

The two children share the parent cur, so they are neighbours.

For each cur that has a next

cur->right->next = cur->next->left

cur->next is the right neighbour of cur, so its left child is next to cur's right child. This is the only link across parents.

End of a row

leftmost = leftmost->left, and stop when leftmost is null

The row below starts under the leftmost node. In a perfect tree, a node with no left child is a leaf, so there is no row below.

What does the current window add to the answer?

Each child gets its next set exactly once: a left child by its parent's pair, and a right child by the cross link. The rightmost node of each row keeps next = null.

Code & Implementation

optimal.cpp

// class Node { int val; Node *left; Node *right; Node *next; };  (given by LeetCode)
class Solution {
public:
    Node* connect(Node* root) {
        // The first node of the level we are linking.
        Node* leftmost = root;

        // In a perfect tree, a node has a left child exactly when it is not a leaf.
        while (leftmost && leftmost->left) {
            // The level above is already linked, so walk this level with next.
            for (Node* cur = leftmost; cur; cur = cur->next) {
                // Same parent: the left child points to the right child.
                cur->left->next = cur->right;
                // Different parents: the right child points to the left child of cur's next neighbour.
                // This is the only place that links across parents.
                if (cur->next) cur->right->next = cur->next->left;
            }
            // Move down one level.
            leftmost = leftmost->left;
        }
        return root;
    }
};

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    public Node(int _val) { val = _val; }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val; left = _left; right = _right; next = _next;
    }
}

class Solution {
    public Node connect(Node root) {
        // The first node of the level we are linking.
        Node leftmost = root;

        // In a perfect tree, a node has a left child exactly when it is not a leaf.
        while (leftmost != null && leftmost.left != null) {
            // The level above is already linked, so walk this level with next.
            for (Node cur = leftmost; cur != null; cur = cur.next) {
                // Same parent: the left child points to the right child.
                cur.left.next = cur.right;
                // Different parents: the right child points to the left child of cur's next neighbour.
                // This is the only place that links across parents.
                if (cur.next != null) cur.right.next = cur.next.left;
            }
            // Move down one level.
            leftmost = leftmost.left;
        }
        return root;
    }
}

from typing import Optional

class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: Optional['Node']) -> Optional['Node']:
        # The first node of the level we are linking.
        leftmost = root

        # In a perfect tree, a node has a left child exactly when it is not a leaf.
        while leftmost and leftmost.left:
            # The level above is already linked, so walk this level with next.
            cur = leftmost
            while cur:
                # Same parent: the left child points to the right child.
                cur.left.next = cur.right
                # Different parents: the right child points to the left child of cur's next neighbour.
                # This is the only place that links across parents.
                if cur.next:
                    cur.right.next = cur.next.left
                cur = cur.next
            # Move down one level.
            leftmost = leftmost.left
        return root

export class _Node {
    val: number;
    left: _Node | null;
    right: _Node | null;
    next: _Node | null;
    constructor(val?: number, left?: _Node | null, right?: _Node | null, next?: _Node | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
        this.next = (next === undefined ? null : next);
    }
}
export { _Node as Node };

export function connect(root: _Node | null): _Node | null {
    // The first node of the level we are linking.
    let leftmost = root;

    // In a perfect tree, a node has a left child exactly when it is not a leaf.
    while (leftmost && leftmost.left) {
        // The level above is already linked, so walk this level with next.
        for (let cur: _Node | null = leftmost; cur !== null; cur = cur.next) {
            // Same parent: the left child points to the right child.
            cur.left!.next = cur.right;
            // Different parents: the right child points to the left child of cur's next neighbour.
            // This is the only place that links across parents.
            if (cur.next) cur.right!.next = cur.next.left;
        }
        // Move down one level.
        leftmost = leftmost.left;
    }
    return root;
}

Complexity

Time O(N)Space O(1)

Every node is handled a constant number of times: each child gets its next set once, by its parent's row. Space is O(1): only leftmost and cur are used. This works because the tree is perfect, so every node above the leaves has two children. The next question (117) has gaps in its tree, so it needs a dummy node.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	BFS with a queue; link each popped node to the front of the queue unless it is the last of its round	O(N)	O(W)
Optimal	Start at the leftmost node; for each node on a row, link its children, plus one cross link to the next parent's left child	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“connect each node to its right neighbour”Each row is a list of nodes. The row above can supply that list through its next pointers.
“perfect binary tree”Every row is full, so each node above the leaves has exactly two children. That lets the walk use cur->left without a null check.
“constant extra space follow-up”No queue. The next pointers we are setting become the queue.

Tree row as a linked list+walk one row with next+link the row below+move down through leftmost→Tree next pointers: level walk with the level above as a linked list

This is level order with the queue replaced by the next pointers. A queue for one row is just the row's nodes in order. Once the row above is linked by next, that row is the list, so no queue is needed. The new part is the cross-parent link (right child → next parent's left child). Populating Next Right Pointers II (LC 117) uses the same walk, but its tree has gaps, so the row below cannot be found from the leftmost node alone.

Don't make this mistake

Forgetting the cross-parent link (5 → 6)

✗ for (Node* cur = leftmost; cur; cur = cur->next) cur->left->next = cur->right;

✓ for (Node* cur = leftmost; cur; cur = cur->next) { cur->left->next = cur->right; if (cur->next) cur->right->next = cur->next->left; }

Node 5 (child of 2) and node 6 (child of 3) have different parents, so the first line never links them. Without the second line, 5's next stays null. The output becomes [1, #, 2, 3, #, 4, 5, #, 6, 7, #], and 5 should point to 6.

Pattern confusion: the queue's front is not always a neighbour

✗ Node* cur = q.front(); q.pop(); cur->next = q.empty() ? nullptr : q.front();

✓ Node* cur = q.front(); q.pop(); if (i + 1 < size) cur->next = q.front(); // i + 1 < size: same round

When a round ends, the front of the queue is the first node of the next row, not a neighbour. On [1, 2, 3, 4, 5, 6, 7], node 3 is the last node of row 1, but the queue already holds 4, so 3 would point to 4. It should be null.

Walking one row too far

✗ for (Node* leftmost = root; leftmost; leftmost = leftmost->left) { ... }

✓ while (leftmost && leftmost->left) { ... leftmost = leftmost->left; }

On the bottom row the leaves have no children, so cur->left is null. The line cur->left->next = cur->right then dereferences a null pointer and crashes. The loop must stop when the row below does not exist.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree BFS translate into production architectures and low-level memory mechanics.

LLD Architecture