algoadvance

Leetcode 116. Populating Next Right Pointers in Each Node

Problem Statement

Given a binary tree:

• Populate each next pointer to point to the next right node.
• If there isn’t a next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example

Input:
     1
   /  \
  2    3
 / \  / \
4  5  6  7

Output:
     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

Constraints

• The number of nodes in the tree is in the range [0, 2^12 - 1].
• The tree is a perfect binary tree, i.e., all leaves are at the same level, and every parent has two children.

Clarifying Questions

1. Directly connecting BFS nodes?
   • Should I use a level-order traversal to connect the nodes, or is there a specific way you prefer the nodes to be connected?
2. Tree properties?
   • Given that it’s a perfect binary tree, I assume I can use this property to simplify the code and logic?

Strategy

To populate each next pointer:

1. Use BFS Approach (Queue-based Level Order Traversal) to connect each node:
   • Initialize a queue with the root node.
   • For each level, connect nodes from left to right using the queue.
   • Push the children of these nodes to the queue for the next level.

The perfect binary tree property allows us to simplify this by:

• Connecting child nodes at the same level without needing extensive checks.

Code

// 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;
    }
};

public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        
        Node leftmost = root;
        
        while (leftmost.left != null) {
            Node head = leftmost;
            
            while (head != null) {
                // Connect left -> right
                head.left.next = head.right;
                
                // Connect right -> left of next subtree, if exists
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                // Move to the next node in the current level
                head = head.next;
            }
            
            // Move to the next level
            leftmost = leftmost.left;
        }
        
        return root;
    }
}

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is processed exactly once.
• Space Complexity: O(1), other than the recursive call stack, no additional space proportional to the input size is used. For the queue, the additional space is O(N) in the worst case, where all nodes at the deepest level are stored.

This solution efficiently connects all next pointers in the given binary tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?