LC 0919 [M] Complete Binary Tree Inserter - ALawliet/algorithms GitHub Wiki

in order to make the nodes as far left as possible, we do BFS but we only append/popleft the queue after we check the right side

we don't need the for _ in range(len(Q)) loop because we don't need to store any info about the level

class CBTInserter:

    def __init__(self, root: TreeNode):
        self.root = root
        self.nextToAddQ = deque([]) # nodes with None child
        
        Q = deque([root])
        while Q: 
            node = Q.popleft()
            
            if node.left:
                Q.append(node.left)
                
            if node.right:
                Q.append(node.right)
                
            # pay attention
            if not node.right:
                self.nextToAddQ.append(node)

    def insert(self, v: int) -> int:
        node = self.nextToAddQ[0]
        newNode = TreeNode(v)
        
        if not node.left:
            node.left = newNode
            
        elif not node.right:
            node.right = newNode
            
        # pay attention
        if node.right:
            self.nextToAddQ.popleft()
            
        self.nextToAddQ.append(newNode)
        return node.val 

    def get_root(self) -> TreeNode:
        return self.root