Populate Tree Next Pointers II [NON PERFECT TREE]

117.Populating Next Right Pointers in Each Node II

Tree

Binary Tree

Linked List

Breadth-First Search

Problem Statement:

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. The tree may not be perfect (nodes can be missing at any level).

Example:

Input:

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

→

Output:

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

# indicates next pointer is pointing to NULL

Algorithm:

1. Process tree level by level using next pointers
2. Maintain head pointer for next level
3. Use prev pointer to connect nodes
4. Handle both left and right children separately

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public Node connect(Node root) {
    if (root == null) return null;

    Node current = root;
    Node nextLevelHead = null;
    Node prev = null;

    // Process each level
    while (current != null) {
        nextLevelHead = null;
        prev = null;
        
        // Process all nodes at current level
        while (current != null) {
            // Handle left child
            if (current.left != null) {
                if (prev != null) 
                    prev.next = current.left;
                else 
                    nextLevelHead = current.left;
                prev = current.left;
            }

            // Handle right child
            if (current.right != null) {
                if (prev != null) 
                    prev.next = current.right;
                else 
                    nextLevelHead = current.right;
                prev = current.right;
            }

            current = current.next;
        }

        // Move to next level
        current = nextLevelHead;
    }
    return root;
}

Python Solution:

def connect(self, root: Node) -> Node:
    if not root:
        return None
        
    current = root
    
    # Process each level
    while current:
        next_level_head = None
        prev = None
        
        # Process all nodes at current level
        while current:
            # Handle left child
            if current.left:
                if prev:
                    prev.next = current.left
                else:
                    next_level_head = current.left
                prev = current.left
            
            # Handle right child
            if current.right:
                if prev:
                    prev.next = current.right
                else:
                    next_level_head = current.right
                prev = current.right
                
            current = current.next
            
        # Move to next level
        current = next_level_head
        
    return root

C++ Solution:

Node* connect(Node* root) {
    if (!root) return nullptr;
    
    Node* current = root;
    Node* nextLevelHead = nullptr;
    Node* prev = nullptr;
    
    // Process each level
    while (current) {
        nextLevelHead = nullptr;
        prev = nullptr;
        
        // Process all nodes at current level
        while (current) {
            // Handle left child
            if (current->left) {
                if (prev)
                    prev->next = current->left;
                else
                    nextLevelHead = current->left;
                prev = current->left;
            }
            
            // Handle right child
            if (current->right) {
                if (prev)
                    prev->next = current->right;
                else
                    nextLevelHead = current->right;
                prev = current->right;
            }
            
            current = current->next;
        }
        
        // Move to next level
        current = nextLevelHead;
    }
    return root;
}