Populating Next Right Pointers in Each Node solution and explanation
Google
9 more videos on this problem
Populating Next Right Pointers in Each Node - Leetcode 116 - PythonNeetCode · 9:49 · 61K views
LeetCode 116 | Populating Next Right Pointers in Each NodeXavier Elon · 6:53 · 7K views
Populating Next Right Pointers in Each Node | Live Coding with Explanation | Leetcode #116Algorithms Made Easy · 3:42 · 5K views
Populating Next Right Pointers in Each Node | LeetCode 116Programming Tutorials · 12:04 · 4K views
Populating Next Right Pointers in Each Node | Leet code 116 | Theory explained + Python codeSai Anish Malla · 14:44 · 4K views
populating next right pointers in each node leetcode | leetcode 116 | bfs level orderNaresh Gupta · 12:04 · 3K views
Populating Next Right Pointers in Each Node | Leetcode 116 | leetcode solutionEasyLeetcode · 12:09 · 587 views
LeetCode 116 - Populating Next Right Pointers in Each Node #leetcodeMushu · 5:40 · 404 views
LeetCode 116. Populating Next Right Pointers in Each NodeHappy Coding · 16:58 · 316 views
Populate Next Right Pointers in Each Node | DSA Series : L.106Shradha Khapra · 11:12 · 22K views
The problem
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
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,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect 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, 212 - 1]. -1000 <= Node.val <= 1000
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: Given a perfect binary tree, connect every node's next pointer to its immediate neighbor on the same level. If there is no neighbor, the pointer should be NULL. The tree structure guarantees every parent has two children and all leaves are on the same level.
Approach 1: Level Order Traversal (Breadth-First Search) (Time: O(n), Space: O(n))
This approach processes the tree level by level using a queue. Push the root into the queue, then iterate through nodes level-wise. For each level, track the previous node and set its next pointer to the current node as you dequeue elements. After finishing a level, the last node naturally points to NULL. This method is straightforward and works for any binary tree, which makes it a good general template for problems involving level relationships. It directly uses Breadth-First Search on a Binary Tree.
Approach 2: Recursive Method (Time: O(n), Space: O(h))
The recursive strategy takes advantage of the perfect binary tree structure. For each node, connect node.left.next = node.right. Then connect across subtrees using node.right.next = node.next.left if the parent has a neighbor. Recursively apply the same logic to left and right children. The key insight: once a node's next pointer is set, it can be used to bridge connections across subtrees. This approach uses Depth-First Search and avoids an explicit queue.
Recommended for interviews: The BFS approach is the safest starting point because it works for both perfect and general binary trees. However, interviewers often expect the recursive solution for this specific problem since it leverages the perfect-tree constraint and reduces auxiliary space. Demonstrating BFS first shows correctness and clarity; transitioning to the recursive pointer-linking approach shows deeper understanding.
Approach 1: Level Order Traversal (Breadth-First Search)
This approach involves using a queue to perform a level order traversal of the tree. At each level of the tree, we'll connect the 'next' pointers of all nodes at that level. Since it is a perfect binary tree, each node at a level is directly followed by its sibling or by NULL if it is the last node at that level.
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
current = root
while current.left:
head = current
while head:
head.left.next = head.right
if head.next:
head.right.next = head.next.left
head = head.next
current = current.left
return rootclass Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
}
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Node current = root;
while (current.left != null) {
Node head = current;
while (head != null) {
head.left.next = head.right;
if (head.next != null) {
head.right.next = head.next.left;
}
head = head.next;
}
current = current.left;
}
return root;
}
}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) {
if (!root) return NULL;
Node* current = root;
while (current->left) {
Node* head = current;
while (head) {
head->left->next = head->right;
if (head->next) head->right->next = head->next->left;
head = head->next;
}
current = current->left;
}
return root;
}
};function Node(val, left, right, next) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
this.next = next === undefined ? null : next;
};
var connect = function(root) {
if (!root) return null;
let current = root;
while (current.left !== null) {
let head = current;
while (head !== null) {
head.left.next = head.right;
if (head.next) {
head.right.next = head.next.left;
}
head = head.next;
}
current = current.left;
}
return root;
};#include <stdlib.h>
struct Node {
int val;
struct Node *left;
struct Node *right;
struct Node *next;
};
void connect(struct Node* root) {
if (!root) return;
struct Node* current = root;
while (current->left) {
struct Node* head = current;
while (head) {
head->left->next = head->right;
if (head->next) {
head->right->next = head->next->left;
}
head = head->next;
}
current = current->left;
}
}public class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() { }
public Node(int _val) { val = _val; }
}
public class Solution {
public Node Connect(Node root) {
if (root == null) return null;
Node current = root;
while (current.left != null) {
Node head = current;
while (head != null) {
head.left.next = head.right;
if (head.next != null) {
head.right.next = head.next.left;
}
head = head.next;
}
current = current.left;
}
return root;
}
}This Python solution uses two pointers, 'current' for moving level-wise and 'head' for node-wise traversal within a level to connect subsequent next pointers.
Time Complexity: O(N), where N is the total number of nodes.
Space Complexity: O(1), as no extra space is employed aside from pointers.
Approach 2: Recursive Method
The recursive method explores the tree depth-first and connects nodes level-wise. This approach effectively utilizes the call stack for traversal, aligning with the tree's inherent properties.
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 or not root.left:
return root
root.left.next = root.right
if root.next:
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
return rootclass Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
}
class Solution {
public Node connect(Node root) {
if (root == null || root.left == null)
return root;
root.left.next = root.right;
if (root.next != null)
root.right.next = root.next.left;
connect(root.left);
connect(root.right);
return root;
}
}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:
void connectNodes(Node* node) {
if (!node || !node->left) return;
node->left->next = node->right;
if (node->next) node->right->next = node->next->left;
connectNodes(node->left);
connectNodes(node->right);
}
Node* connect(Node* root) {
connectNodes(root);
return root;
}
};function Node(val, left, right, next) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
this.next = next === undefined ? null : next;
};
var connect = function(root) {
if (!root || !root.left) return root;
root.left.next = root.right;
if (root.next) root.right.next = root.next.left;
connect(root.left);
connect(root.right);
return root;
};#include <stdlib.h>
struct Node {
int val;
struct Node *left;
struct Node *right;
struct Node *next;
};
void connect(struct Node* root) {
if (!root || !root->left) return;
root->left->next = root->right;
if (root->next) {
root->right->next = root->next->left;
}
connect(root->left);
connect(root->right);
}public class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() { }
public Node(int _val) { val = _val; }
}
public class Solution {
public Node Connect(Node root) {
if (root == null || root.left == null)
return root;
root.left.next = root.right;
if (root.next != null)
root.right.next = root.next.left;
Connect(root.left);
Connect(root.right);
return root;
}
}Using Python, this code adopts recursion to connect nodes, ensuring each level progresses with accurately distributed next pointers, thanks to the inherent recursive nature.
Time Complexity: O(N), for visiting each node.
Space Complexity: O(logN), dictated by the recursion stack.
Approach 3: BFS
Use a queue for level order traversal, and each time you traverse a level, 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 == null || root.left == null) {
return root;
}
const { left, right, next } = root;
left.next = right;
if (next != null) {
right.next = next.left;
}
connect(left);
connect(right);
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: DFS
Use recursion for preorder traversal, and each time you traverse to a node, connect its left and right child nodes in order.
Specifically, we design a function dfs(left, right), which points the next pointer of the left node to the right node. In the function, we first check whether left and right are null. If both are not null, point left.next to right, and then recursively call dfs(left.left, left.right), dfs(left.right, right.left), dfs(right.left, right.right).
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 == null) {
return root;
}
const queue = [root];
while (queue.length !== 0) {
const n = queue.length;
let pre = null;
for (let i = 0; i < n; i++) {
const node = queue.shift();
node.next = pre;
pre = node;
const { left, right } = node;
left && queue.push(right, left);
}
}
return root;
}/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/
func connect(root *Node) *Node {
var dfs func(*Node, *Node)
dfs = func(left, right *Node) {
if left == nil || right == nil {
return
}
left.Next = right
dfs(left.Left, left.Right)
dfs(left.Right, right.Left)
dfs(right.Left, right.Right)
}
if root != nil {
dfs(root.Left, root.Right)
}
return root
}Complexity comparison
| Approach | Complexity |
|---|---|
| Level Order Traversal (Breadth-First Search) | Time Complexity: O(N), where N is the total number of nodes. |
| Recursive Method | Time Complexity: O(N), for visiting each node. |
| BFS | – |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal (BFS) | O(n) | O(n) | Best for clarity and works for any binary tree structure |
| Recursive Pointer Linking | O(n) | O(h) | Optimal for perfect binary trees where sibling relationships are guaranteed |
Frequently asked questions
Is Populating Next Right Pointers in Each Node easy or hard?
The problem is classified as Medium. The BFS solution is relatively straightforward, but the recursive pointer-linking technique requires recognizing the perfect binary tree property and carefully linking nodes across subtrees.
How to solve Populating Next Right Pointers in Each Node in O(n)?
Traverse the tree once and connect nodes during traversal. Using BFS, process nodes level by level and link consecutive nodes in the queue. Using recursion, connect node.left.next to node.right and node.right.next to node.next.left when available. Both approaches ensure each node is processed once.
Populating Next Right Pointers in Each Node Python or Java solution
Python and Java implementations usually follow either BFS with a queue or a recursive DFS approach. BFS iterates through each level and links nodes sequentially, while recursion connects children directly using node.left, node.right, and node.next references.
What is the best approach for Populating Next Right Pointers in Each Node?
The recursive pointer-linking approach is typically considered the best for this problem because the tree is guaranteed to be perfect. It connects node.left to node.right and uses the parent’s next pointer to connect across subtrees. This runs in O(n) time and uses O(h) space due to recursion.
What data structure is used in Populating Next Right Pointers in Each Node?
The main data structure is a binary tree with an additional next pointer in each node. BFS solutions use a queue to process levels, while DFS solutions rely on recursion and existing next pointers to connect neighboring nodes.
What is the time complexity of Populating Next Right Pointers in Each Node?
Both common solutions run in O(n) time because every node in the binary tree is visited exactly once. BFS uses a queue to process nodes level by level, while the recursive DFS solution links children directly using already established next pointers.
Is Populating Next Right Pointers in Each Node asked at Google, Amazon, or Meta?
Populating Next Right Pointers in Each Node frequently appears in technical interviews at companies like Google, Amazon, and Meta because it tests tree traversal, pointer manipulation, and understanding of level relationships in binary trees.