117. Populating Next Right Pointers in Each Node II

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

1. Base Case: If the root is None, return None.
2. Queue Initialization: Use a list to simulate a queue for the level-order traversal. Start by adding the root node to the queue.
3. 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, or None 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.
4. 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;
};