LeetCode 117: Populating Next Right Pointers in Each Node II Solution

Master LeetCode problem 117 (Populating Next Right Pointers in Each Node II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

117. Populating Next Right Pointers in Each Node II

Medium

Linked List Tree Depth-First Search Breadth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a level order traversal of the binary tree and connect the nodes at each level using the next pointer. We can use a queue to keep track of the nodes at each level and connect them accordingly.

Start with the root node.
Initialize a queue and add the root node to it.
While the queue is not empty, iterate through the nodes at the current level and connect them using the next pointer.
Add the children nodes of the current level to the queue for processing in the next iteration.
Repeat the process until all levels are processed.

Time Complexity: O(N) where N is the number of nodes in the binary tree.

Space Complexity: O(N) in the worst case where all nodes are at the same level.

Solution Code

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                Node current = queue.poll();
                
                if (i < size - 1) {
                    current.next = queue.peek();
                }
                
                if (current.left != null) queue.offer(current.left);
                if (current.right != null) queue.offer(current.right);
            }
        }
        
        return root;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 117 (Populating Next Right Pointers in Each Node II)?

This page provides optimized solutions for LeetCode problem 117 (Populating Next Right Pointers in Each Node II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 117 (Populating Next Right Pointers in Each Node II)?

The time complexity for LeetCode 117 (Populating Next Right Pointers in Each Node II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 117 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 117 in Java, C++, or Python.

Back to LeetCode Solutions