Populating Next Right Pointers in Each Node II

Problem Description

Given a binary tree:

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.

Examples

Example 1:
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: The serialized output is in level order, where # signifies a path terminator where no node exists.

Example 2:
Input: root = []
Output: []

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


"""
# 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
"""
def connect(root: 'Node') -> 'Node':
    if not root:
        return None
    
    # Start with the first level
    current = root
    
    while current:
        # Dummy node to help build the next level
        dummy = Node(0)
        # Tail of the next level being built
        tail = dummy
        
        # Iterate through nodes at current level
        while current:
            if current.left:
                tail.next = current.left
                tail = tail.next
            if current.right:
                tail.next = current.right
                tail = tail.next
            current = current.next
        
        # Move to the next level
        current = dummy.next
    
    return root

Java Solution


/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        
        // Start with the first level
        Node current = root;
        
        while (current != null) {
            // Dummy node to help build the next level
            Node dummy = new Node(0);
            // Tail of the next level being built
            Node tail = dummy;
            
            // Iterate through nodes at current level
            while (current != null) {
                if (current.left != null) {
                    tail.next = current.left;
                    tail = tail.next;
                }
                if (current.right != null) {
                    tail.next = current.right;
                    tail = tail.next;
                }
                current = current.next;
            }
            
            // Move to the next level
            current = dummy.next;
        }
        
        return root;
    }
}

C++ Solution


/*
// Definition for a Node.
class Node {
public:
    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) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) {
            return nullptr;
        }
        
        // Start with the first level
        Node* current = root;
        
        while (current) {
            // Dummy node to help build the next level
            Node* dummy = new Node(0);
            // Tail of the next level being built
            Node* tail = dummy;
            
            // Iterate through nodes at current level
            while (current) {
                if (current->left) {
                    tail->next = current->left;
                    tail = tail->next;
                }
                if (current->right) {
                    tail->next = current->right;
                    tail = tail->next;
                }
                current = current->next;
            }
            
            // Move to the next level
            current = dummy->next;
            delete dummy;  // Clean up dummy node
        }
        
        return root;
    }
};

JavaScript Solution


/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if (!root) {
        return null;
    }
    
    // Start with the first level
    let current = root;
    
    while (current) {
        // Dummy node to help build the next level
        const dummy = new Node(0);
        // Tail of the next level being built
        let tail = dummy;
        
        // Iterate through nodes at current level
        while (current) {
            if (current.left) {
                tail.next = current.left;
                tail = tail.next;
            }
            if (current.right) {
                tail.next = current.right;
                tail = tail.next;
            }
            current = current.next;
        }
        
        // Move to the next level
        current = dummy.next;
    }
    
    return root;
};

C# Solution


/*
// Definition for a Node.
public class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
*/
public class Solution {
    public Node Connect(Node root) {
        if (root == null) {
            return null;
        }
        
        // Start with the first level
        Node current = root;
        
        while (current != null) {
            // Dummy node to help build the next level
            Node dummy = new Node(0);
            // Tail of the next level being built
            Node tail = dummy;
            
            // Iterate through nodes at current level
            while (current != null) {
                if (current.left != null) {
                    tail.next = current.left;
                    tail = tail.next;
                }
                if (current.right != null) {
                    tail.next = current.right;
                    tail = tail.next;
                }
                current = current.next;
            }
            
            // Move to the next level
            current = dummy.next;
        }
        
        return root;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the tree
Space Complexity: O(1) as we only use constant extra space

Solution Explanation

This solution uses a level-by-level approach with a dummy node:

Key concept:
- Level-wise traversal
- Dummy node technique
- Next pointer linking
Algorithm steps:
- Process each level
- Use dummy node
- Connect child nodes
- Move to next level

Key points:

Constant extra space
Handle missing nodes
Level-wise linking
Efficient traversal