Complete Binary Tree Inserter Interview Question for Google

# Complete Binary Tree Inserter

## Problem Description

The problem requires designing a `CBTInserter` class that can insert new nodes into a complete binary tree while maintaining its completeness. A complete binary tree is a binary tree where every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

The `CBTInserter` class should have the following methods:

*   `CBTInserter(TreeNode root)`: Initializes the data structure with the root of the complete binary tree.
*   `int insert(int v)`: Inserts a `TreeNode` with value `v` into the tree, maintaining completeness, and returns the value of the parent of the inserted node.
*   `TreeNode get_root()`: Returns the root node of the tree.

## Naive Approach

A naive approach would involve traversing the tree to find the appropriate location to insert the new node. We can perform a level-order traversal to find the first node that has either a missing left child or a missing right child. Inserting the new node there ensures the tree remains complete.

## Optimal Approach

To optimize the insertion process, we can maintain a queue of nodes that are potential parents for new nodes. These are nodes that have either a missing left or right child. During insertion, we check the front of the queue. If the node at the front has a missing left child, we insert the new node as its left child. If the left child is present but the right child is missing, we insert the new node as its right child. Once a node has both left and right children, it is removed from the queue, as it is no longer a potential parent. We also need to add the new node to the queue since it might need children.

```python
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class CBTInserter:

    def __init__(self, root: TreeNode):
        self.root = root
        self.queue = deque()
        q = deque([root])
        while q:
            node = q.popleft()
            if not node.left or not node.right:
                self.queue.append(node)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

    def insert(self, val: int) -> int:
        node = TreeNode(val)
        parent = self.queue[0]
        if not parent.left:
            parent.left = node
        else:
            parent.right = node
            self.queue.popleft()
        self.queue.append(node)
        return parent.val

    def get_root(self) -> TreeNode:
        return self.root


# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(val)
# param_2 = obj.get_root()

Big(O) Runtime Analysis

CBTInserter(TreeNode root): The constructor performs a level-order traversal of the tree, which takes O(N) time, where N is the number of nodes in the tree. The while loop processes each node once, leading to a runtime proportional to the number of nodes. Appending and popping from deque are O(1). Therefore, the overall runtime is O(N).
insert(int v): The insert function has a time complexity of O(1) because it performs a constant number of operations: accessing the front of the queue, creating a new node, inserting the node, and potentially removing a node from the front of the queue and appending the new node to the end. These are all constant-time operations.
get_root(): The get_root function simply returns the root node, which takes O(1) time.

Big(O) Space Usage Analysis

CBTInserter(TreeNode root): The constructor uses a queue to store potential parent nodes. In the worst-case scenario, where the last level of the tree is only partially filled, the queue can contain nodes from the last two levels. In a complete binary tree, the number of nodes at the last level can be up to N/2. Thus, the space complexity of the queue can be O(N) in the worst case. Therefore, the overall space complexity is O(N).
insert(int v): The insert function creates a new TreeNode, which takes O(1) space. It also adds the new node to the queue, but this does not change the overall space complexity, as the queue's size is still bounded by O(N).
get_root(): The get_root function uses O(1) space because it only returns the root node without using any additional memory.

Edge Cases

Empty Tree: If the input tree is empty (root is None), the constructor should handle this case gracefully. The provided code will fail if the root is None. A check for the root being None should be included, and the root should be initialized with the first inserted value. The queue would be initialized with the new root node.
Large Number of Insertions: The queue may grow large if there are many insertions. The code is designed to handle a large number of insertions efficiently because the insert operation is O(1).
Duplicate Values: The problem statement does not specify any constraints against duplicate values. Therefore, the code will work correctly with duplicate values.
Invalid Input: The problem statement assumes that the input tree is a valid complete binary tree. If the input tree is not a valid CBT, the algorithm might not behave as expected. However, based on the problem constraints, this case doesn't need to be explicitly handled.