algoadvance

Leetcode 117. Populating Next Right Pointers in Each Node II

Problem Statement

You are given a binary tree where each node has the following structure:

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

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.

Clarifying Questions

1. Does the input binary tree have any constraints? For example, is it a perfect binary tree?
   • No, it is not necessarily a perfect binary tree; it’s a general binary tree.
2. Can we use additional memory for this operation, or should it be done in-place?
   • The problem doesn’t restrict the use of additional memory explicitly, but an in-place solution is preferred to optimize for space complexity.
3. Is the tree empty (i.e., the root node is null) a valid input?
   • Yes, the tree can be empty, and in that case, the output should also be null.

Strategy

1. Use a level-order traversal (BFS) to connect the next pointers on each level.
2. Use a dummy node for each level to manage the connections smoothly.
3. Keep track of the current level’s nodes using a pointer and link their children appropriately.

Code

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        
        Node current = root;
        Node dummy = new Node(0); // Dummy node for each level
        Node tail = dummy; // Tail pointer for the current level list
        
        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;
            if (current == null) {
                current = dummy.next;
                dummy.next = null;
                tail = dummy;
            }
        }
        
        return root;
    }
}

Time Complexity

• The time complexity of this solution is (O(n)), where (n) is the number of nodes in the binary tree. The algorithm processes each node exactly once.

• The space complexity is (O(1)) for the dummy and tail pointers, not including the recursion stack. Since we’re doing it in place and not using extra space proportional to the number of nodes, it’s considered (O(1)) space complexity.

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?