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:
[0, 212 - 1].-1000 <= Node.val <= 1000Follow-up:
In #116 Populating Next Right Pointers in Each Node, the goal is to connect every node in a binary tree to its immediate right neighbor at the same level using a next pointer. If no neighbor exists, the pointer should be set to null.
A common strategy is Breadth-First Search (BFS). Using a queue, traverse the tree level by level. For each level, connect nodes sequentially by updating their next pointers before moving to the next level. This approach is intuitive and works for typical interview scenarios.
Another optimized approach leverages already established next pointers to traverse levels without extra data structures. By linking children across adjacent parents, the tree can be processed in-place with constant extra space.
The BFS solution typically runs in O(n) time with additional space for the queue, while the pointer-based level traversal can achieve O(1) auxiliary space while still visiting each node once.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS Level Order Traversal (Queue) | O(n) | O(n) |
| In-place Level Traversal using Next Pointers | O(n) | O(1) |
NeetCode
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.
Time Complexity: O(N), where N is the number of nodes, since each node is processed once.
Space Complexity: O(1), as no extra space other than pointers is used—the perfect use of a constant space solution.
1class Node {
2public:
3 int val;
4 Node* left;
5 Node* right;
6 Node* next;
7
8 Node() : val(0), left(NULL), right(NULL), next(NULL) {}
9 Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
10};
11
12class Solution {
13public:
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;
}
};This C++ solution uses 'current' to traverse each level, and 'head' to travel across nodes in each level, connecting left to right and next to left of the succeeding nodes. The process moves downwards.
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.
Time Complexity: O(N), which implies visiting each node once.
Space Complexity: O(logN) for recursion stack, since depth is proportional to the logarithm of node count.
1public:
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;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations frequently appear in FAANG-style interviews. It tests understanding of tree traversal, pointer manipulation, and space optimization techniques in binary trees.
BFS naturally processes nodes level by level, which aligns with the requirement to connect nodes horizontally. By iterating through each level sequentially, you can easily set the next pointer of each node to its right neighbor.
A queue is often used to perform breadth-first traversal of the binary tree. It helps process nodes level by level so their next pointers can be connected correctly. In optimized solutions, the tree structure itself is used without additional data structures.
A common optimal approach is level-order traversal using BFS. It connects nodes within the same level by tracking them in a queue and linking each node to the next node in that level. An even more optimized approach uses already established next pointers to traverse levels with constant extra space.
The C++ solution uses a helper method 'connectNodes' to recursively connect nodes in the left and right subtrees, maintaining the recursive call depth with the log of the number of nodes.