Populate Binary Tree Next Pointers I [PERFECT binary tree]

116.Populating Next Right Pointers in Each Node

Tree

Binary Tree

Breadth-First Search

Linked List

Problem Statement:

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. 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.

Example:

Input:

root = [1,2,3,4,5,6,7]

→

Output:

[1,#,2,3,#,4,5,6,7,#]

# indicates next pointer is pointing to NULL

Algorithm:

1. BFS Solution: Use queue to track nodes level by level
2. Optimal Solution: Use next pointers already created
3. For optimal, connect left to right child first
4. Then connect right child to next node's left child

Complexity:

BFS: Time O(n), Space O(n) | Optimal: Time O(n), Space O(1)

Java Solution:

// BFS Solution with queue
public Node connect(Node root) {
    if (root == null) return null;
    
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    
    // Process level by level
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node prev = null;
        
        // Connect all nodes at current level
        for (int i = 0; i < size; i++) {
            Node curr = queue.poll();
            if (prev != null) prev.next = curr;
            prev = curr;
            
            // Add children for next level
            if (curr.left != null) queue.add(curr.left);
            if (curr.right != null) queue.add(curr.right);
        }
    }
    return root;
}

// Optimal Solution without extra space
public Node connect(Node root) {
    if (root == null) return null;
    
    Node leftmost = root;
    
    // Process until we reach last level
    while (leftmost.left != null) {
        Node current = leftmost;
        
        // Connect nodes at current level
        while (current != null) {
            // Connect across same parent
            current.left.next = current.right;
            
            // Connect across different parents
            if (current.next != null) {
                current.right.next = current.next.left;
            }
            current = current.next;
        }
        leftmost = leftmost.left;
    }
    return root;
}

Python Solution:

# BFS Solution with queue
def connect(self, root: Optional[Node]) -> Optional[Node]:
    if not root:
        return None
        
    queue = deque([root])
    
    # Process level by level
    while queue:
        size = len(queue)
        prev = None
        
        # Connect all nodes at current level
        for _ in range(size):
            curr = queue.popleft()
            if prev:
                prev.next = curr
            prev = curr
            
            # Add children for next level
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
                
    return root

# Optimal Solution without extra space
def connect(self, root: Optional[Node]) -> Optional[Node]:
    if not root:
        return None
        
    leftmost = root
    
    # Process until we reach last level
    while leftmost.left:
        current = leftmost
        
        # Connect nodes at current level
        while current:
            # Connect across same parent
            current.left.next = current.right
            
            # Connect across different parents
            if current.next:
                current.right.next = current.next.left
            current = current.next
            
        leftmost = leftmost.left
        
    return root

C++ Solution:

class Solution {
public:
    // BFS Solution with queue
    Node* connect(Node* root) {
        if (!root) return nullptr;
        
        queue<Node*> q;
        q.push(root);
        
        // Process level by level
        while (!q.empty()) {
            int size = q.size();
            Node* prev = nullptr;
            
            // Connect all nodes at current level
            for (int i = 0; i < size; i++) {
                Node* curr = q.front();
                q.pop();
                
                if (prev) prev->next = curr;
                prev = curr;
                
                // Add children for next level
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
        return root;
    }
    
    // Optimal Solution without extra space
    Node* connect(Node* root) {
        if (!root) return nullptr;
        
        Node* leftmost = root;
        
        // Process until we reach last level
        while (leftmost->left) {
            Node* current = leftmost;
            
            // Connect nodes at current level
            while (current) {
                // Connect across same parent
                current->left->next = current->right;
                
                // Connect across different parents
                if (current->next) {
                    current->right->next = current->next->left;
                }
                current = current->next;
            }
            leftmost = leftmost->left;
        }
        return root;
    }
};