Populating Next Right Pointers in Each Node II solution and explanation
Google
9 more videos on this problem
Populating Next Right Pointers in Each Node II | Live Coding with Explanation | Leetcode - 117Algorithms Made Easy · 8:16 · 27K views
[Java] Leetcode 117. Populating Next Right Pointers in Each Node II [Binary Tree #4]Eric Programming · 9:58 · 8K views
LeetCode 117. Populating Next Right Pointers in Each Node IIHappy Coding · 17:58 · 6K views
Populating Next Right Pointers in Each Node II | Leetcode 117 | Cakewalk BFS | Live coding sessionCoding Decoded · 7:47 · 2K views
Leetcode 117. Populating Next Right Pointers II | Simplest CodeThinkCode · 5:31 · 1K views
LeetCode 117. [Medium with HARD followup] Populating Next Right Pointers in Each Node IIFrancesco Manicardi · 5:39 · 1K views
Leetcode 117. Populating Next Right Pointers in Each Node IIPlacement Corner · 11:10 · 903 views
Daily Leetcode #773: May 13, 2022 - 117. Populating Next Right Pointers in Each Node IIProgramming Live with Larry · 5:44 · 774 views
Populating Next Right Pointers in Each Node II | Leetcode 117 | FAANG interview questionSuper Lazy Coder · 15:16 · 682 views
Leetcode 117. Populating Next Right Pointers in Each Node II. BFS. PythonShen Zheng · 8:30 · 457 views
The problem
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
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.
Example 1:
Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
Example 2:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 6000]. -100 <= Node.val <= 100
Follow-up:
- You may only use constant extra space.
- The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
Approach overview
Problem Overview: You are given a binary tree where each node contains an extra next pointer. The task is to connect every node to its immediate neighbor on the same level. If there is no neighbor, the next pointer should be set to null. Unlike the simpler version of the problem, the tree is not guaranteed to be perfect, so children may appear in any structure.
Approach 1: Level Order Traversal Using a Queue (O(n) time, O(n) space)
This approach performs a standard Breadth-First Search level traversal. Push the root into a queue, then process nodes level by level. For each level, iterate through the nodes currently in the queue and connect the previous node's next pointer to the current node. Children of the current node are pushed into the queue so the next level can be processed afterward. Because every node is visited exactly once, the time complexity is O(n). The queue may hold up to the maximum width of the tree, giving O(n) worst-case space complexity.
This method is straightforward and mirrors how levels are naturally processed in a binary tree. It is often the first solution developers implement because the logic is simple: track the previous node in the level and link it to the current one.
Approach 2: Using Constant Space (Two Pointers) (O(n) time, O(1) extra space)
The optimized solution eliminates the queue by using the already established next pointers to traverse levels. Maintain two pointers: one for scanning the current level and another for building the next level. A temporary dummy node acts as the head of the next level while a tail pointer attaches children as they are discovered.
Start with the root as the current level. Iterate through nodes using their next pointers. Whenever a node has a left or right child, attach it to the tail of the next-level chain and advance the tail pointer. Once the current level is finished, move to dummy.next, which represents the start of the next level, and repeat the process.
This technique effectively performs a level traversal without extra storage. Each node is processed once, so the time complexity remains O(n). Since only a few pointers are used regardless of tree size, the auxiliary space complexity is O(1). The idea resembles pointer-based traversal patterns often seen in DFS style tree problems, but applied level-by-level.
Recommended for interviews: Start with the queue-based BFS explanation because it clearly demonstrates how level connections work. Then transition to the constant-space two-pointer approach. Interviewers typically expect the O(1) extra space solution since it shows strong understanding of pointer manipulation and tree traversal patterns.
Approach 1: Approach 1: Level Order Traversal Using a Queue
This approach uses a breadth-first search (BFS) strategy by employing a queue to keep track of nodes at the current level and connect their children nodes from left to right. After processing all nodes on a level, we move to the children (if any), ensuring the next pointers are correctly set.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return None
queue = deque([root])
while queue:
size = len(queue)
prev = None
for i in range(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 rootimport java.util.LinkedList;
import java.util.Queue;
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 void connect(Node root) {
if (root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
Node prev = null;
for (int i = 0; i < size; i++) {
Node curNode = queue.poll();
if (prev != null) prev.next = curNode;
prev = curNode;
if (curNode.left != null) queue.add(curNode.left);
if (curNode.right != null) queue.add(curNode.right);
}
}
}
}#include <iostream>
#include <queue>
using namespace std;
struct Node {
int val;
Node *left;
Node *right;
Node *next;
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
};
void connect(Node* root) {
if (!root) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
Node* prev = NULL;
for (int i = 0; i < 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);
}
// last node's next is already NULL since it was initialized
}
}function Node(val, left, right, next) {
this.val = val;
this.left = left;
this.right = right;
this.next = next;
};
var connect = function(root) {
if (!root) return null;
let queue = [];
queue.push(root);
while (queue.length) {
let size = queue.length;
let prev = null;
for (let i = 0; i < size; i++) {
let 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;
};#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
struct Node *left;
struct Node *right;
struct Node *next;
};
struct Queue {
struct Node **data;
int front, rear, size, capacity;
};
struct Queue* createQueue(int capacity) {
struct Queue* queue = malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->data = malloc(queue->capacity * sizeof(struct Node*));
return queue;
}
int isEmpty(struct Queue* queue) {
return (queue->size == 0);
}
void enqueue(struct Queue* queue, struct Node* node) {
queue->rear = (queue->rear + 1)%queue->capacity;
queue->data[queue->rear] = node;
queue->size = queue->size + 1;
}
struct Node* dequeue(struct Queue* queue) {
struct Node* node = queue->data[queue->front];
queue->front = (queue->front + 1)%queue->capacity;
queue->size = queue->size - 1;
return node;
}
void connect(struct Node *root) {
if (!root) return;
struct Queue* queue = createQueue(6000);
enqueue(queue, root);
while (!isEmpty(queue)) {
int size = queue->size;
struct Node *prev = NULL;
for (int i = 0; i < size; i++) {
struct Node *node = dequeue(queue);
if (prev) prev->next = node;
prev = node;
if (node->left) enqueue(queue, node->left);
if (node->right) enqueue(queue, node->right);
}
if (prev) prev->next = NULL;
}
free(queue->data);
free(queue);
}using System;
using System.Collections.Generic;
public 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;
}
}
public class Solution {
public void Connect(Node root) {
if (root == null) return;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count > 0) {
int size = queue.Count;
Node prev = null;
for (int i = 0; i < size; i++) {
Node node = queue.Dequeue();
if (prev != null) prev.next = node;
prev = node;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
if (prev != null) prev.next = null;
}
}
}Using the deque structure from Python's collections module, this solution effectively conducts a level-order traversal to set each node's next pointer. This is achieved by linking nodes within the same level.
Time Complexity: O(n), where n is the count of nodes.
Space Complexity: O(n), attributed to the deque storage for the nodes.
Approach 2: Approach 2: Using Constant Space (Two Pointers)
This approach leverages a two-pointer or head-tail strategy to eliminate the need for extra storage space beyond two pointers. The idea is to work with two nested loops; an outer loop goes level by level, and an inner loop connects nodes within the same level by their next pointers.
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: 'Node') -> 'Node':
current = root
dummy = Node(0)
while current:
tail = dummy
dummy.next = None
while current:
if current.left:
tail.next = current.left
tail = tail.next
if current.right:
tail.next = current.right
tail = tail.next
current = current.next
current = dummy.next
return rootclass Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
}
class Solution {
public void connect(Node root) {
Node current = root;
Node head = new Node(0);
while (current != null) {
Node tail = head;
head.next = null;
while (current != null) {
if (current.left != null) {
tail.next = current.left;
tail = tail.next;
}
if (current.right != null) {
tail.next = current.right;
tail = tail.next;
}
current = current.next;
}
current = head.next;
}
}
}#include <iostream>
using namespace std;
struct Node {
int val;
Node *left;
Node *right;
Node *next;
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
};
void connect(Node* root) {
if (!root) return;
Node* current = root;
Node dummy(0);
Node* tail = &dummy;
while (current) {
dummy.next = NULL;
tail = &dummy;
while (current) {
if (current->left) {
tail->next = current->left;
tail = tail->next;
}
if (current->right) {
tail->next = current->right;
tail = tail->next;
}
current = current->next;
}
current = dummy.next;
}
}function Node(val, left, right, next) {
this.val = val;
this.left = left;
this.right = right;
this.next = next;
};
var connect = function(root) {
let current = root;
let dummy = new Node(0);
while (current !== null) {
let tail = dummy;
dummy.next = null;
while (current !== null) {
if (current.left !== null) {
tail.next = current.left;
tail = tail.next;
}
if (current.right !== null) {
tail.next = current.right;
tail = tail.next;
}
current = current.next;
}
current = dummy.next;
}
return root;
};#include <stdio.h>
struct Node {
int val;
struct Node *left;
struct Node *right;
struct Node *next;
};
void connect(struct Node *root) {
if (!root) return;
struct Node *head = root;
while (head) {
struct Node *nextHead = NULL, *prev = NULL;
for (struct Node *current = head; current; current = current->next) {
if (current->left) {
if (prev) prev->next = current->left;
else nextHead = current->left;
prev = current->left;
}
if (current->right) {
if (prev) prev->next = current->right;
else nextHead = current->right;
prev = current->right;
}
}
head = nextHead;
}
}public class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
}
public class Solution {
public void Connect(Node root) {
Node current = root;
Node dummy = new Node(0, null, null, null);
while (current != null) {
Node tail = dummy;
dummy.next = null;
while (current != null) {
if (current.left != null) {
tail.next = current.left;
tail = tail.next;
}
if (current.right != null) {
tail.next = current.right;
tail = tail.next;
}
current = current.next;
}
current = dummy.next;
}
}
}Python code utilizes two loops: the first traverses each level, and the second inside loop sets the next pointers for every node by using a dummy head node for bookkeeping the start of the next level.
Time Complexity: O(n), given each node is visited once.
Space Complexity: O(1), implementing only pointer replacements and no extra memory for containers.
Approach 3: BFS
We use a queue q for level order traversal. Each time we traverse a level, we connect the nodes of the current level in order.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for Node.
* class Node {
* val: number
* left: Node | null
* right: Node | null
* next: Node | null
* constructor(val?: number, left?: Node, right?: Node, next?: Node) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function connect(root: Node | null): Node | null {
if (!root) {
return null;
}
const q: Node[] = [root];
while (q.length) {
const nq: Node[] = [];
let p: Node | null = null;
for (const node of q) {
if (p) {
p.next = node;
}
p = node;
const { left, right } = node;
left && nq.push(left);
right && nq.push(right);
}
q.splice(0, q.length, ...nq);
}
return root;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/
func connect(root *Node) *Node {
if root == nil {
return root
}
q := []*Node{root}
for len(q) > 0 {
var p *Node
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
if p != nil {
p.Next = node
}
p = node
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
}
return root
}Approach 4: Space Optimization
The space complexity of Solution 1 is relatively high because it requires a queue to store the nodes of each level. We can implement it with constant space.
We define two pointers prev and next, which point to the previous node and the first node of the next level, respectively. When traversing the nodes of the current level, we string the nodes of the next level together and find the first node of the next level. After the current level is traversed, we assign the first node next of the next level to node and continue to traverse.
The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).
/**
* Definition for Node.
* class Node {
* val: number
* left: Node | null
* right: Node | null
* next: Node | null
* constructor(val?: number, left?: Node, right?: Node, next?: Node) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function connect(root: Node | null): Node | null {
const modify = (curr: Node | null): void => {
if (!curr) {
return;
}
next = next || curr;
if (prev) {
prev.next = curr;
}
prev = curr;
};
let node = root;
let [prev, next] = [null, null];
while (node) {
while (node) {
modify(node.left);
modify(node.right);
node = node.next;
}
node = next;
[prev, next] = [null, null];
}
return root;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/
func connect(root *Node) *Node {
node := root
var prev, next *Node
modify := func(curr *Node) {
if curr == nil {
return
}
if next == nil {
next = curr
}
if prev != nil {
prev.Next = curr
}
prev = curr
}
for node != nil {
prev, next = nil, nil
for node != nil {
modify(node.Left)
modify(node.Right)
node = node.Next
}
node = next
}
return root
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Level Order Traversal Using a Queue | Time Complexity: O(n), where n is the count of nodes. |
| Approach 2: Using Constant Space (Two Pointers) | Time Complexity: O(n), given each node is visited once. |
| BFS | – |
| Space Optimization | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal Using Queue | O(n) | O(n) | Best when clarity matters. Easy to implement and reason about during interviews. |
| Constant Space Two-Pointer Traversal | O(n) | O(1) | Preferred in interviews when minimizing auxiliary space is required. |
Frequently asked questions
Is Populating Next Right Pointers in Each Node II easy or hard?
The problem is rated Medium on LeetCode. The BFS solution is straightforward, but the constant-space solution requires careful pointer handling across levels, which increases the difficulty slightly.
Populating Next Right Pointers in Each Node II Python/Java solution
Python and Java implementations usually follow either BFS with a queue or the constant-space pointer technique. Both versions iterate through levels, connect adjacent nodes, and ensure the last node in each level points to null.
How to solve Populating Next Right Pointers in Each Node II in O(n)?
Traverse the tree level by level. During traversal, connect nodes within the same level either by storing nodes in a queue or by using existing next pointers to iterate horizontally. Each node is processed one time, giving O(n) time complexity.
What is the best approach for Populating Next Right Pointers in Each Node II?
The most efficient approach uses a constant-space two-pointer technique. It traverses each level using existing next pointers while building the next level with a dummy head and tail pointer. This processes all nodes in O(n) time and O(1) extra space, making it the preferred interview solution.
Is Populating Next Right Pointers in Each Node II asked at Google/Amazon/Meta?
Tree pointer manipulation and level traversal problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem are commonly used to evaluate understanding of BFS traversal and pointer-based tree techniques.
What data structure is used in Populating Next Right Pointers in Each Node II?
The primary data structure is a binary tree. Solutions typically use a queue for Breadth-First Search or pointer manipulation to traverse levels without additional storage. The optimized approach relies on linking nodes using the existing next pointers.
What is the time complexity of Populating Next Right Pointers in Each Node II?
Both common approaches run in O(n) time because every node in the binary tree is visited exactly once. The queue-based BFS uses O(n) space in the worst case, while the optimized two-pointer solution reduces the extra space to O(1).