Complete Binary Tree Inserter

Intuition

We could keep all node whose left node or right node is empty in a queue and once inserting a new node, add it to the top of the queue's left or right.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque


class CBTInserter:
    def __init__(self, root: TreeNode):
        self.root = root
        self.queue = deque([root])
        while self.queue[0].left and self.queue[0].right:
            node = self.queue.popleft()
            self.queue.append(node.left)
            self.queue.append(node.right)

    def insert(self, v: int) -> int:
        node = TreeNode(v)
        self.queue.append(node)
        if self.queue[0].left is None:
            self.queue[0].left = node
            return self.queue[0].val
        elif self.queue[0].right is None:
            self.queue[0].right = node
            return self.queue.popleft().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(v)
# param_2 = obj.get_root()