Complete Binary Tree Inserter - Leetcode Solution

The Complete Binary Tree Inserter problem on leetcode requires you to implement a class that can insert nodes into a complete binary tree. A complete binary tree is one where every level except the last is completely filled, and all nodes are as far left as possible. Here are the steps to solve this problem:

1. Create a class called CBTInserter that takes in the root of a complete binary tree as its constructor argument.

2. In the constructor, traverse the tree level by level and store all the nodes in a list or queue. You can use breadth-first search to traverse the tree level by level.

3. Implement the insert method that takes in an integer value v and inserts it as a new node into the complete binary tree. To do this, append a new node with the given value to the end of the list of nodes. Calculate the index of the parent node for the new node using integer division and subtracting 1 from the index to account for 0-based indexing. Then set the parent of the new node as the node at the calculated parent index.

4. Implement the get_root method that returns the root of the complete binary tree.

Here's the full implementation of the CBTInserter class:

class CBTInserter:
    def __init__(self, root: TreeNode):
        self.nodes = []
        # breadth-first search to traverse the tree level by level
        queue = [root]
        while queue:
            node = queue.pop(0)
            if node:
                self.nodes.append(node)
                queue.append(node.left)
                queue.append(node.right)

    def insert(self, v: int) -> int:
        node = TreeNode(v)
        self.nodes.append(node)
        parent_index = (len(self.nodes) - 2) // 2
        parent = self.nodes[parent_index]
        if not parent.left:
            parent.left = node
        else:
            parent.right = node
        return parent.val

    def get_root(self) -> TreeNode:
        return self.nodes[0]

Note that in the insert method, we return the value of the parent node, not the newly inserted node. This is because the problem statement only requires us to return the value of the parent node, not the node itself.

Overall, the time complexity of this implementation is O(log N) for insertions and O(1) for get_root, where N is the number of nodes in the tree. The space complexity is O(N) for storing all the nodes in the list.

1