🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem can be visualized as connecting all nodes on the same level from left to right. A level-order traversal (or breadth-first traversal) is suitable for this purpose, as it processes nodes level by level. By maintaining the order of nodes in each level, we can easily set the next
pointer for each node.
Approach
- Base Case: If the root is
None
, returnNone
. - Queue Initialization: Use a list to simulate a queue for the level-order traversal. Start by adding the root node to the queue.
- Level Order Traversal:
- Use a while loop to process nodes level by level until the queue is empty.
- For each node in the current level:
- Set its
next
pointer to the next node in the queue, orNone
if it is the last node in the level. - Add its left and right children to the next level's queue. - Update the queue to the next level's queue after processing all nodes in the current level. - Return the Root: After all nodes have been connected, return the root node.
Complexity
Time Complexity:
O(n)
, where n
is the number of nodes in the tree. Each node is processed once.
Space Complexity:
O(n)
in the worst case, where the queue might contain all nodes in the last level of the tree.
Code
C++
class Solution {
public:
Node* connect(Node* root) {
if (!root) return nullptr;
std::queue queue;
queue.push(root);
while (!queue.empty()) {
std::queue newQueue;
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node* node = queue.front();
queue.pop();
if (node) {
if (node->left) newQueue.push(node->left);
if (node->right) newQueue.push(node->right);
node->next = (i < size - 1) ? queue.front() : nullptr;
}
}
queue = newQueue;
}
return root;
}
};
Python
# 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
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return None
queue = [root]
while queue:
next_level = []
for i in range(len(queue)):
node = queue[i]
if i < len(queue) - 1:
node.next = queue[i + 1]
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
queue = next_level
return root
Java
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
if (i < size - 1) {
node.next = queue.peek();
}
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
return root;
}
}
JavaScript
var connect = function(root)
{
let queue = [];
queue.push(root);
while (queue.length)
{
let newQueue = [];
for (let i = 0; i < queue.length; i++) {
let node = queue[i];
if (node) {
if (node.left) newQueue.push(node.left);
if (node.right) newQueue.push(node.right);
node.next = queue[i+1] || null;
}
}
queue = newQueue;
}
return root;
};