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.


&nbsp;
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]


&nbsp;
Constraints:


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


class CBTInserter:

    def __init__(self, root: Optional[TreeNode]):
        self.root = root
        self.queue = Queue()
        self.queue.put(self.root)
        self.parent_of_last_inserted = None
        
    def insert(self, val: int) -> int:
        if self.parent_of_last_inserted is not None and self.parent_of_last_inserted.right is None:
            self.parent_of_last_inserted.right = TreeNode(val)
            self.queue.put(self.parent_of_last_inserted.right)
            return self.parent_of_last_inserted.val
        
        while not self.queue.empty():
            node = self.queue.get()
            if node.left is None:
                node.left = TreeNode(val)
                self.queue.put(node.left)
                self.parent_of_last_inserted = node
                return node.val
            else:
                self.queue.put(node.left)
            if node.right is None:
                node.right = TreeNode(val)
                self.queue.put(node.right)
                self.parent_of_last_inserted = node
                return node.val
            else:
                self.queue.put(node.right)
        

    def get_root(self) -> Optional[TreeNode]:
        return self.root
class CBTInserter {

    private TreeNode root;
    private int total;

    private int count(TreeNode root) {
        if (root == null) return 0;
        return 1+count(root.left)+count(root.right);
    }

    public CBTInserter(TreeNode root) {
        this.root = root;
        total = count(root);
    }

    private int insertBinary(int val, int k, int right) {
        int left = 0;
        var ptr = root;
        while (left < right) {
            if (left == right -1) {
                if (ptr.left == null) ptr.left = new TreeNode(val);
                else ptr.right = new TreeNode(val);
                return ptr.val;
            }
            int mid = (right-left) / 2 + left;
            if (mid >= k ) {
                ptr = ptr.left;
                right = mid;
            } else if (mid < k) {
                left = mid+1;
                ptr = ptr.right;
            }
        }
        return 0;
    }

    public int insert(int val) {
        int depth = 0;
        int n = total;
        while(n > 0) {
            depth++;
            n /= 2;
        }
        if ((1<<depth)-1 == total) depth++;
        // k is the new index in the lowest level of tree, right is the max index of the lowest level of tree
        // e.g. for tree
        // 1
        // / \
        // 2 new
//index 0 1
        // it's insertBinary(val, 1, 1)
        var res = insertBinary(val, total - (1<<(depth-1))+1 , (1<<(depth-1)) -1);
        total++;
        return res;
    }

    public TreeNode get_root() {
        return root;
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class CBTInserter {
public:
    vector<TreeNode*> arr;

    CBTInserter(TreeNode* root) {

        arr.push_back(root);
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){

            if(q.front() -> left != NULL){
                arr.push_back(q.front() -> left);
                q.push(q.front() -> left);
            }
            if(q.front() -> right != NULL){
                arr.push_back(q.front() -> right);
                q.push(q.front() -> right);
            }
            q.pop();

        }
    }

    int insert(int val) {

        TreeNode* new_node = new TreeNode(val);
        arr.push_back(new_node);
        int parent_index = (arr.size()-2)/2;
        if(2*parent_index +1 == arr.size()-1){arr[parent_index] -> left = new_node;}
        else{arr[parent_index] -> right = new_node;}
        return arr[parent_index] -> val;
    }

    TreeNode* get_root() {
        return arr[0];
    }
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(val);
 * TreeNode* param_2 = obj->get_root();
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 */
var CBTInserter = function(root) {
    this.root = root;
};

/** 
 * @param {number} val
 * @return {number}
 */
CBTInserter.prototype.insert = function(val) {
    let cur = this.root;
    let queue = [cur];
    while(queue.length){
        let updatedQueue = [];
        while(queue.length){
            let node = queue.shift();
            if(!node.left) {
                node.left = new TreeNode(val);
                return node.val;
            }
            else updatedQueue.push(node.left);
            if(!node.right) {
                node.right = new TreeNode(val);
                return node.val;
            }
            else updatedQueue.push(node.right);
        }
        queue = updatedQueue ;
    }
    
};

/**
 * @return {TreeNode}
 */
CBTInserter.prototype.get_root = function() {
    return this.root;
};

/** 
 * Your CBTInserter object will be instantiated and called as such:
 * var obj = new CBTInserter(root)
 * var param_1 = obj.insert(val)
 * var param_2 = obj.get_root()
 */
Complete Binary Tree Inserter