Complete Binary Tree Inserter LeetCode solution in Python

1
from collections import deque
2

3

4
class CBTInserter:
5

6
    def __init__(self, root: TreeNode):
7

8
        self.root = root
9

10
        self.parent_keeper = deque([root])
11

12
        while True:
13

14
            cur = self.parent_keeper[0]
15

16
            if cur:
17

18
                if cur.left:
19

20
                    self.parent_keeper.append(cur.left)
21

22
                    if cur.right:
23

24
                        self.parent_keeper.append(cur.right)
25

26
                        # cur is completed with two child, pop out
27
                        self.parent_keeper.popleft()
28

29
                    else:
30
                        # parent of next insertion is found, stop
31
                        break
32

33
                else:
34
                    # parent of next insertion is found, stop
35
                    break
36

37
    def insert(self, v: int) -> int:
38

39
        parent = self.parent_keeper[0]
40

41
        # Insert with leftward compact, to meet the definition of complete binary tree
42

43
        if not parent.left:
44
            parent.left = TreeNode(v)
45
            self.parent_keeper.append(parent.left)
46
        else:
47
            parent.right = TreeNode(v)
48
            self.parent_keeper.append(parent.right)
49

50
            # current parent is completed with two child now, pop parent from parent keeper on the head
51
            self.parent_keeper.popleft()
52

53
        return parent.val
54

55
    def get_root(self) -> TreeNode:
56

57
        return self.root