Populating Next Right Pointers in Each Node II

Problem Statement

Given a binary tree (not necessarily perfect), populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

What to notice first

• Unlike #116 (perfect binary tree), this is for any binary tree structure.
• The tree may have missing nodes, making alignment trickier.
• Both approaches use the property that a parent’s level is already connected before processing children.

Examples

Input	Output	Explanation
[1,2,3,4,5,null,7]	Next pointers at level 2 connect 4→5 and 5→7	Nodes at same level connected; null skipped
[1,2,3]	Simple tree: level 2 has 2→3	Both nodes present, connection straightforward

Constraints

• The number of nodes is in the range [0, 6000].
• -100 <= Node.val <= 100

Real-World Applications

Where this pattern appears

• Tree serialization — traversing levels for compact binary representation.
• Breadth-first processing — needing siblings at same level quickly.
• Memory layout optimization — cache-aware tree traversal linking related data.

Complexity Comparison

Approach	Time	Space	Best When
Level-Order Queue	O(n)	O(w)	Simple, clear level traversal; w is max width
Pre-Computed Links	O(n)	O(1)	Memory-constrained; use parent-level links to traverse

Which approach should you learn first?

• Learn Level-Order Queue first — it is straightforward and intuitive.
• Study Pre-Computed Links to master O(1) space without extra queue.

O(1) Space Optimal

Pre-Computed Links

O(n) time · O(1) space

Clear & Intuitive

Level-Order Queue

O(n) time · O(w) space

Approach 1: Level-Order Queue BFS

★ Recommended

Use a queue to process nodes level-by-level. For each level, connect consecutive nodes’ next pointers.

⏱ Time O(n) Visit each node once 💾 Space O(w) Queue stores max level width

Step-by-step Example

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

Step	Action	Result
Level 0	Process node 1	Node 1 next = NULL
Level 1	Process nodes 2, 3	Connect 2 → 3
Level 2	Process nodes 4, 5, 7	Connect 4 → 5 → 7 (skip null)

Pseudocode

function connect(root):
    if not root: return root
    queue = [root]

    while queue not empty:
        levelSize = queue.length
        prev = null

        for i in 0..levelSize-1:
            node = queue.pop()
            if prev: prev.next = node
            prev = node

            if node.left: queue.push(node.left)
            if node.right: queue.push(node.right)

    return root

Solution Code

Python

populating_next_right_pointers_ii_queue.py

from typing import Optional
from collections import deque


# Definition for a Node.
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


def connect(root: Optional[Node]) -> Optional[Node]:
    """
    Populates next pointers in a perfect binary tree using level-order BFS queue.
    Time: O(n), Space: O(w) where w is max width
    """
    if not root:
        return root

    queue = deque([root])

    while queue:
        level_size = len(queue)
        prev = None

        for i in range(level_size):
            node = queue.popleft()

            if prev:
                prev.next = node
            prev = node

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return root


# Test cases
if __name__ == "__main__":
    # Example 1: Perfect binary tree
    root = Node(1,
                Node(2, Node(4), Node(5)),
                Node(3, Node(6), Node(7)))
    result = connect(root)
    print("Example 1: Tree with next pointers connected via queue")

    # Example 2: Single node
    single = Node(1)
    result = connect(single)
    print("Example 2: Single node tree")

    # Example 3: None
    result = connect(None)
    print("Example 3: None input")

C++

populating_next_right_pointers_ii_queue.cpp

#include <queue>
using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        /**
         * Populates next pointers using level-order BFS queue.
         * Time: O(n), Space: O(w) where w is max width
         */
        if (!root) return root;

        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            int level_size = q.size();
            Node* prev = NULL;

            for (int i = 0; i < level_size; i++) {
                Node* node = q.front();
                q.pop();

                if (prev) {
                    prev->next = node;
                }
                prev = node;

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }

        return root;
    }
};

// Test cases
int main() {
    // Example 1: Tree with next pointers connected
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(7);

    Solution sol;
    sol.connect(root);
    cout << "Example 1: Tree with next pointers connected via queue" << endl;

    return 0;
}

Java

PopulatingNextRightPointersIIQueue.java

import java.util.Queue;
import java.util.LinkedList;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    public Node(int _val) {
        val = _val;
    }
}

class Solution {
    /**
     * Populates next pointers using level-order BFS queue.
     * Time: O(n), Space: O(w) where w is max width
     */
    public Node connect(Node root) {
        if (root == null) return root;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            Node prev = null;

            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();

                if (prev != null) {
                    prev.next = node;
                }
                prev = node;

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }

        return root;
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: Tree with next pointers connected
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(7);

        Solution sol = new Solution();
        sol.connect(root);
        System.out.println("Example 1: Tree with next pointers connected via queue");
    }
}

JavaScript

populating_next_right_pointers_ii_queue.js

/**
 * Definition for a Node.
 */
class Node {
    constructor(val = 0, left = null, right = null, next = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

/**
 * Populates next pointers using level-order BFS queue.
 * Time: O(n), Space: O(w) where w is max width
 * @param {Node} root
 * @return {Node}
 */
function connect(root) {
    if (!root) return root;

    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        let prev = null;

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();

            if (prev) {
                prev.next = node;
            }
            prev = node;

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return root;
}

// Test cases
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(7);

connect(root);
console.log("Example 1: Tree with next pointers connected via queue");

Rust

populating_next_right_pointers_ii_queue.rs

use std::collections::VecDeque;
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct Node {
    pub val: i32,
    pub left: Option<Rc<RefCell<Node>>>,
    pub right: Option<Rc<RefCell<Node>>>,
    pub next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node {
            val,
            left: None,
            right: None,
            next: None,
        }
    }
}

/**
 * Populates next pointers using level-order BFS queue.
 * Time: O(n), Space: O(w) where w is max width
 */
pub fn connect(mut root: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
    if root.is_none() {
        return None;
    }

    let mut queue = VecDeque::new();
    queue.push_back(root.clone());

    while !queue.is_empty() {
        let level_size = queue.len();
        let mut prev: Option<Rc<RefCell<Node>>> = None;

        for _ in 0..level_size {
            if let Some(node) = queue.pop_front() {
                if let Some(p) = prev.clone() {
                    p.borrow_mut().next = Some(node.clone());
                }
                prev = Some(node.clone());

                let node_ref = node.borrow();
                if let Some(left) = node_ref.left.clone() {
                    queue.push_back(left);
                }
                if let Some(right) = node_ref.right.clone() {
                    queue.push_back(right);
                }
            }
        }
    }

    root
}

fn main() {
    println!("Example 1: Tree with next pointers connected via queue");
}

Go

populating_next_right_pointers_ii_queue.go

package main

import "fmt"

/**
 * Definition for a Node.
 */
type Node struct {
    Val   int
    Left  *Node
    Right *Node
    Next  *Node
}

/**
 * Populates next pointers using level-order BFS queue.
 * Time: O(n), Space: O(w) where w is max width
 */
func connect(root *Node) *Node {
    if root == nil {
        return root
    }

    queue := []*Node{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        var prev *Node

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            if prev != nil {
                prev.Next = node
            }
            prev = node

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }

    return root
}

func main() {
    fmt.Println("Example 1: Tree with next pointers connected via queue")
}

Approach 2: Pre-Computed Links O(1) Space

optimal

Use next pointers from the parent level to traverse the current level, eliminating the queue.

⏱ Time O(n) Visit each node once 💾 Space O(1) Only pointers, no extra storage

Step-by-step Example

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

Step	Using	Connects
Level 1	root’s structure	2 → 3
Level 2	2.next (= 3)	4 → 5 → 7

Pseudocode

function connect(root):
    if not root: return root
    leftmost = root

    while leftmost:
        prev = null
        current = leftmost

        while current:
            if current.left:
                if prev: prev.next = current.left
                prev = current.left

            if current.right:
                if prev: prev.next = current.right
                prev = current.right

            current = current.next

        leftmost = leftmost.left

    return root

Solution Code

Python

populating_next_right_pointers_ii_precomputed_links.py

from typing import Optional


# Definition for a Node.
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


def connect(root: Optional[Node]) -> Optional[Node]:
    """
    Populates next pointers using pre-computed links without extra queue.
    Uses next pointers of parent level to traverse current level.
    Time: O(n), Space: O(1)
    """
    if not root:
        return root

    leftmost = root

    while leftmost:
        prev = None
        current = leftmost

        while current:
            if current.left:
                if prev:
                    prev.next = current.left
                prev = current.left

            if current.right:
                if prev:
                    prev.next = current.right
                prev = current.right

            current = current.next

        leftmost = leftmost.left

    return root


# Test cases
if __name__ == "__main__":
    # Example 1: Perfect binary tree
    root = Node(1,
                Node(2, Node(4), Node(5)),
                Node(3, Node(6), Node(7)))
    result = connect(root)
    print("Example 1: Tree with next pointers connected via pre-computed links")

    # Example 2: Single node
    single = Node(1)
    result = connect(single)
    print("Example 2: Single node tree")

    # Example 3: None
    result = connect(None)
    print("Example 3: None input")

C++

populating_next_right_pointers_ii_precomputed_links.cpp

#include <iostream>
using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        /**
         * Populates next pointers using pre-computed links without queue.
         * Uses next pointers of parent level to traverse current level.
         * Time: O(n), Space: O(1)
         */
        if (!root) return root;

        Node* leftmost = root;

        while (leftmost) {
            Node* prev = NULL;
            Node* current = leftmost;

            while (current) {
                if (current->left) {
                    if (prev) {
                        prev->next = current->left;
                    }
                    prev = current->left;
                }

                if (current->right) {
                    if (prev) {
                        prev->next = current->right;
                    }
                    prev = current->right;
                }

                current = current->next;
            }

            leftmost = leftmost->left;
        }

        return root;
    }
};

// Test cases
int main() {
    // Example 1: Tree with next pointers connected
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(7);

    Solution sol;
    sol.connect(root);
    cout << "Example 1: Tree with next pointers connected via pre-computed links" << endl;

    return 0;
}

Java

PopulatingNextRightPointersIIPrecomputedLinks.java

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    public Node(int _val) {
        val = _val;
    }
}

class Solution {
    /**
     * Populates next pointers using pre-computed links without queue.
     * Uses next pointers of parent level to traverse current level.
     * Time: O(n), Space: O(1)
     */
    public Node connect(Node root) {
        if (root == null) return root;

        Node leftmost = root;

        while (leftmost != null) {
            Node prev = null;
            Node current = leftmost;

            while (current != null) {
                if (current.left != null) {
                    if (prev != null) {
                        prev.next = current.left;
                    }
                    prev = current.left;
                }

                if (current.right != null) {
                    if (prev != null) {
                        prev.next = current.right;
                    }
                    prev = current.right;
                }

                current = current.next;
            }

            leftmost = leftmost.left;
        }

        return root;
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: Tree with next pointers connected
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(7);

        Solution sol = new Solution();
        sol.connect(root);
        System.out.println("Example 1: Tree with next pointers connected via pre-computed links");
    }
}

JavaScript

populating_next_right_pointers_ii_precomputed_links.js

/**
 * Definition for a Node.
 */
class Node {
    constructor(val = 0, left = null, right = null, next = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}

/**
 * Populates next pointers using pre-computed links without queue.
 * Uses next pointers of parent level to traverse current level.
 * Time: O(n), Space: O(1)
 * @param {Node} root
 * @return {Node}
 */
function connect(root) {
    if (!root) return root;

    let leftmost = root;

    while (leftmost) {
        let prev = null;
        let current = leftmost;

        while (current) {
            if (current.left) {
                if (prev) {
                    prev.next = current.left;
                }
                prev = current.left;
            }

            if (current.right) {
                if (prev) {
                    prev.next = current.right;
                }
                prev = current.right;
            }

            current = current.next;
        }

        leftmost = leftmost.left;
    }

    return root;
}

// Test cases
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(7);

connect(root);
console.log("Example 1: Tree with next pointers connected via pre-computed links");

Rust

populating_next_right_pointers_ii_precomputed_links.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct Node {
    pub val: i32,
    pub left: Option<Rc<RefCell<Node>>>,
    pub right: Option<Rc<RefCell<Node>>>,
    pub next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node {
            val,
            left: None,
            right: None,
            next: None,
        }
    }
}

/**
 * Populates next pointers using pre-computed links without queue.
 * Uses next pointers of parent level to traverse current level.
 * Time: O(n), Space: O(1)
 */
pub fn connect(mut root: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
    if root.is_none() {
        return None;
    }

    let mut leftmost = root.clone();

    while let Some(lm) = leftmost.clone() {
        let mut prev: Option<Rc<RefCell<Node>>> = None;
        let mut current = Some(lm.clone());

        while let Some(curr) = current.clone() {
            let curr_ref = curr.borrow();

            if let Some(left) = curr_ref.left.clone() {
                if let Some(p) = prev.clone() {
                    p.borrow_mut().next = Some(left.clone());
                }
                prev = Some(left);
            }

            if let Some(right) = curr_ref.right.clone() {
                if let Some(p) = prev.clone() {
                    p.borrow_mut().next = Some(right.clone());
                }
                prev = Some(right);
            }

            current = curr_ref.next.clone();
        }

        let lm_ref = lm.borrow();
        leftmost = lm_ref.left.clone();
    }

    root
}

fn main() {
    println!("Example 1: Tree with next pointers connected via pre-computed links");
}

Go

populating_next_right_pointers_ii_precomputed_links.go

package main

import "fmt"

/**
 * Definition for a Node.
 */
type Node struct {
    Val   int
    Left  *Node
    Right *Node
    Next  *Node
}

/**
 * Populates next pointers using pre-computed links without queue.
 * Uses next pointers of parent level to traverse current level.
 * Time: O(n), Space: O(1)
 */
func connect(root *Node) *Node {
    if root == nil {
        return root
    }

    leftmost := root

    for leftmost != nil {
        var prev *Node
        current := leftmost

        for current != nil {
            if current.Left != nil {
                if prev != nil {
                    prev.Next = current.Left
                }
                prev = current.Left
            }

            if current.Right != nil {
                if prev != nil {
                    prev.Next = current.Right
                }
                prev = current.Right
            }

            current = current.Next
        }

        leftmost = leftmost.Left
    }

    return root
}

func main() {
    fmt.Println("Example 1: Tree with next pointers connected via pre-computed links")
}

Watch for these pitfalls

• Forgetting to handle null children — skip them but still link the next non-null child.
• Not resetting prev correctly at each level boundary.
• Using level-order queue when O(1) space solution exists.

Related Problems

• Populating Next Right Pointers in Each Node ↗ Medium #116
• Binary Tree Level Order Traversal ↗ Medium #102
• Minimum Depth of Binary Tree ↗ Easy #111

Interview Tips

Key trade-offs to discuss

• Why Level-Order Queue? It is intuitive and handles irregular trees well.
• Why Pre-Computed Links? Demonstrates O(1) space mastery and efficient tree manipulation.
• Edge cases: Root is null, single node, tree with only left/right children.
• Follow-up: How would you handle a graph with arbitrary parent pointers?

← Previous
#114 Flatten Binary Tree to Linked List Next
#120 Triangle →