919. Complete Binary Tree Inserter

Problem Link

Description

---

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.

Implement the CBTInserter class:

• CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree.
• int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode.
• TreeNode get_root() Returns the root node of the tree.

 

Example 1:

Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]
Explanation
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3);  // return 1
cBTInserter.insert(4);  // return 2
cBTInserter.get_root(); // return [1, 2, 3, 4]

 

Constraints:

• The number of nodes in the tree will be in the range [1, 1000].
• 0 <= Node.val <= 5000
• root is a complete binary tree.
• 0 <= val <= 5000
• At most 104 calls will be made to insert and get_root.

Solution

---

Python3

# Definition for a binary tree node.
# 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.A = deque()
        
        dq = deque()
        if root:
            dq.append(root)
        
        while dq:
            node = dq.popleft()
            self.A.append(node)
            
            for child in (node.left, node.right):
                if child:
                    dq.append(child)
 
    def insert(self, val: int) -> int:
        while self.A and self.A[0].left and self.A[0].right:
            self.A.popleft()
        
        node = TreeNode(val)
        curr = self.A[0]
        
        if not curr.left:
            curr.left = node
        elif not curr.right:
            curr.right = node
            self.A.popleft()
        
        self.A.append(node)
        
        return curr.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()