#919

Complete Binary Tree Inserter

specialist · 640 · lc medium +30 · 65% accepted · 1,154 likes · top 69%

Description

A complete binary tree has every level fully filled except possibly the last, where nodes are packed as far left as possible. Implement CBTInserter to support efficient insertion while preserving completeness:

- CBTInserter(TreeNode root) initializes with an existing complete binary tree.

- int insert(int val) adds a new node with value val and returns the value of its parent.

- TreeNode get_root() returns the current root of the tree.

Example 1:

Input

["CBTInserter", "insert", "insert", "get_root"]

[[[1, 2]], [3], [4], []]

Output

[null, 1, 2, [1, 2, 3, 4]]

Example 2:

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]

Code

# 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]):
        

    def insert(self, val: int) -> int:
        

    def get_root(self) -> Optional[TreeNode]:
        


# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(val)
# param_2 = obj.get_root()

# 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]):
        

    def insert(self, val: int) -> int:
        

    def get_root(self) -> Optional[TreeNode]:
        


# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(val)
# param_2 = obj.get_root()