algoadvance

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.

Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"4"},"right":{"$id":"5"},"val":2},"right":{"$id":"3","right":{"$id":"7"},"val":3},"val":1}
Output: {"$id":"1","left":{"$id":"2","left":{"$id":"4"},"next":{"$id":"3"},"right":{"$id":"5"},"val":2},"next":null,"right":{"$id":"3","next":null,"right":{"$id":"7"},"val":3},"val":1}

Note:

• You may only use constant extra space.
• Recursive approach is fine, implicit stack space does not count as extra space for this problem.

Clarifying Questions

1. Can we assume that the tree can have any number of levels?
2. Should we handle cases where the input binary tree is empty?

Strategy

1. Level Order Traversal using Pointers: We will use a level-order traversal approach (similar to breadth-first search) to connect each node to the next right node.
2. Dummy Node: The main idea is to use a dummy node that helps us connect nodes at the current level. We will iterate through the current level and establish connections for the next level.
3. Pointer Manipulation: We will use a current node to traverse through the current level and a tail pointer to build the next pointers for the next level.
4. Upstream to Next Level: Once the iteration of the current level is done, we move to the next level using the dummy’s next pointer.

Code

class Node:
    def __init__(self, val: int, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        
        # Start with the root node
        current = root
        
        while current:
            # Use a dummy node to establish the 'next' connections of the next level
            dummy = Node(0)
            tail = dummy
            
            # Iterate over the current level
            while current:
                if current.left:
                    tail.next = current.left
                    tail = tail.next
                if current.right:
                    tail.next = current.right
                    tail = tail.next
                # Move to the next node in the current level
                current = current.next
            
            # Move to the next level
            current = dummy.next
        
        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) for the algorithm itself as we are using a constant amount of extra space. However, the recursion stack space will be O(h) where h is the height of the tree.

This solution efficiently uses pointers to perform the level-order traversal while maintaining the requirement of constant space.

Try our interview co-pilot at AlgoAdvance.com

• 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?