Naive Solution

A brute force approach to solve this problem would involve traversing the entire tree for each insertion to find the appropriate place to add the new node. This would involve:

1. A insert function that traverses the tree.
2. If a node has a missing left or right child, insert the new node there.
3. If the current level is full, proceed to the next level.

The problem with this approach is the time complexity. In the worst-case scenario, we might have to traverse a large portion of the tree to find the correct insertion point.

Big O Runtime: O(n) for each insertion, where n is the number of nodes in the tree, because in the worst case, we may have to search a large part of the tree. Big O Space Usage: O(w), where w is the maximum width of the tree because a queue is used for level order traversal.

Optimal Solution

To optimize, we can keep track of nodes that are potentially the parent of the next inserted node. A queue can be used to store these candidate parent nodes.

Here is the detailed algorithm:

1. Initialization:
   • During the CBTInserter initialization, perform a level-order traversal of the existing tree.
   • Add nodes that do not have both left and right children to a queue.
2. Insert:
   • When inserting a new value:
     • Get the first node p from the queue.
     • Insert the new node as the left child of p if p does not have a left child.
     • Otherwise, insert it as the right child.
     • If we inserted as the right child, p is now full, so remove it from the queue.
     • Add the newly inserted node to the queue, as it might become a parent of a future node.
     • Return the value of the parent p.
3. Get Root:
   • Return the root node.

Edge Cases:

• Empty Tree: Handle the case where the initial tree is empty. The root must be set to the first inserted node.
• Single Node: A single node can easily become the parent of the next two nodes.
• Complete Tree: If the tree is already complete, the queue will be empty upon initialization and all nodes will be added to the bottom level.

Code:

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

Big O Runtime:

• CBTInserter: O(n), where n is the number of nodes in the initial tree (due to the level-order traversal).
• insert: O(1) on average, as we only perform a constant number of operations.
• get_root: O(1)

Big O Space Usage:

• CBTInserter: O(w), where w is the maximum width of the tree (to store nodes in the queue).
• insert: O(1)
• get_root: O(1)