_919. Complete Binary Tree Inserter.md

919. Complete Binary Tree Inserter

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 05, 2024

Last updated : July 05, 2024

---

Related Topics : Tree, Breadth-First Search, Design, Binary Tree

Acceptance Rate : 66.01 %

---

        1
     __/ \__
    2       3
   / \     / \
  4   5   6   7

$$\left \lfloor{\log_{2}(1)}\right \rfloor = lvl = 0$$

$$\left \lfloor{\log_{2}(2)}\right \rfloor = lvl = 1$$

$$\left \lfloor{\log_{2}(3)}\right \rfloor = lvl = 1$$

$$\left \lfloor{\log_{2}(4)}\right \rfloor = lvl = 2$$

$$\left \lfloor{\log_{2}(5)}\right \rfloor = lvl = 2$$

$$\left \lfloor{\log_{2}(6)}\right \rfloor = lvl = 2$$

$$\left \lfloor{\log_{2}(7)}\right \rfloor = lvl = 2$$

Their remainders go as follows:

$$Remainder(1) = 0 = 0b0$$

$$Remainder(2) = 0 = 0b0$$

$$Remainder(3) = 1 = 0b1$$

$$Remainder(4) = 0 = 0b00$$

$$Remainder(5) = 1 = 0b01$$

$$Remainder(6) = 2 = 0b10$$

$$Remainder(7) = 3 = 0b11$$

Ignoring the root, if we take the binary string and read it from left to right (not including the 0b binary indicator), we can find the path to the proper index of the new node where 0 indicates taking the left edge and 1 indicates taking the right edge.

Remainders of $0, 1, 2, 3, \ldots$ indicate indices $0, 1, 2, 3, \ldots$.

---

Solutions

• m919.py

Python

m919.py

# 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: Optional[TreeNode]):
        self.root = root

        def getNodeCount(curr: Optional[TreeNode]) :
            if not curr :
                return
            self.size += 1
            getNodeCount(curr.left)
            getNodeCount(curr.right)

        self.size = 0
        getNodeCount(root)

    def insert(self, val: int) -> int:
        self.size += 1
        lvl = int(log(self.size, 2))
        indx = self.size - 2 ** lvl

        path = bin(indx)
        path = (lvl - len(path) + 2) * '0' + path
        
        curr = self.root
        for direction in path[2:-1] :
            if direction == '1' :
                curr = curr.right
            else :
                curr = curr.left
        if path[-1] == '1' :
            curr.right = TreeNode(val=val)
        else :
            curr.left = TreeNode(val=val)
        return curr.val
        

    def get_root(self) -> Optional[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()