Problem statement

https://leetcode.com/problems/complete-binary-tree-inserter/

Solution

The idea is to keep so-called hot nodes in queue: it is those nodes, to which we need to attach new node. First, to initialize we need to traverse our tree with bfs and put all hot nodes to queue: such that have 0 or 1 children. Then to insert we always look at the first hot node and try to attach to it: first to the left and if it is not possible to the right. If we attached to the right, this node stop being hot, so we remove it from queue. Also we add node to the end of our queue.

Complexity

Time complexity of init is O(m), where m is number of nodes in tree, space complexity as well. Time complexity of insert is O(1), additional space complexity is also O(1).

Code

class CBTInserter:
    def __init__(self, root):
        self.levels = deque()
        queue = deque([root])
        while queue:
            el = queue.popleft()
            if not el.left or not el.right: self.levels.append(el)
            if el.left:  queue.append(el.left)
            if el.right: queue.append(el.right)
        
        self.root = root
        
    def insert(self, v):
        node = TreeNode(v)
        parent = self.levels[0]
        if parent.left:
            parent.right = node
            self.levels.popleft()
        else:
            parent.left = node
        self.levels.append(node)
        return parent.val

    def get_root(self):
        return self.root