Last updated on January 21st, 2025 at 02:22 am
Here, we see a Populating Next Right Pointers in Each Node LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Hash Table, Two-Pointers
Companies
Level of Question
Medium
Populating Next Right Pointers in Each Node LeetCode Solution
Table of Contents
1. Problem Statement
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: []
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Tree Depth First Search (DFS)”. This is because the code traverses the binary tree recursively (in C++, Java, and Python) or level by level (in JavaScript) to connect the next pointers of nodes. The recursive approach in C++, Java, and Python explores the left and right subtrees in a depth-first manner, while the JavaScript implementation uses a queue to perform a level-order traversal, which is a variation of Tree Breadth-First Search (BFS).
3. Code Implementation in Different Languages
3.1 Populating Next Right Pointers in Each Node C++
class Solution {
public:
Node* connect(Node* root) {
if(root == NULL) return NULL;
if(root->left != NULL) root->left->next = root->right;
if(root->right != NULL && root->next != NULL) root->right->next = root->next->left;
connect(root->left);
connect(root->right);
return root;
}
};
3.2 Populating Next Right Pointers in Each Node Java
class Solution {
public Node connect(Node root) {
if(root == null) return null;
if(root.left != null) root.left.next = root.right;
if(root.right != null && root.next != null) root.right.next = root.next.left;
connect(root.left);
connect(root.right);
return root;
}
}
3.3 Populating Next Right Pointers in Each Node JavaScript
var connect = function(root) {
if (root == null) return root;
let queue = [root];
while(queue.length!=0) {
let next = [];
while(queue.length!=0) {
let node = queue.shift();
node.next = queue[0]||null;
if (node.left!=null) {
next.push(node.left);
next.push(node.right);
}
}
queue = next;
}
return root;
};
3.4 Populating Next Right Pointers in Each Node Python
class Solution(object):
def connect(self, root):
if not root:
return
c1, c2 = root.left, root.right
while c1 and c2:
c1.next = c2
c1, c2 = c1.right, c2.left
self.connect(root.left)
self.connect(root.right)
return root
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(h) |
| Java | O(n) | O(h) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(h) |