919. Complete Binary Tree Inserter

T: intit: O(n), insertion O(1)

S: O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class CBTInserter {
    private Queue<TreeNode> insertQueue;
    private TreeNode root;
    public CBTInserter(TreeNode root) {
        this.root = root;
        this.insertQueue = new LinkedList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
            if (cur.left == null || cur.right == null) { // means find "all" empty parent nodes 
                this.insertQueue.offer(cur);
            }
        }
    }
    
    public int insert(int val) { // O(1)
        TreeNode node = insertQueue.peek();
        TreeNode insertNode = new TreeNode(val);
        if (node.left == null) {
            node.left = insertNode;
        } else if (node.right == null) {
            node.right = insertNode;
            insertQueue.poll(); // after adding right nodes, means this parent node is exhausted and has no empty node, so poll it
        }
        insertQueue.offer(insertNode); // new nodes' children nodes are also empty, so add to insertQueue as parent nodes 
        return node.val;
    }
    
    public TreeNode get_root() {
        return this.root;
    }
}

/**
 * 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();




 insert: O(n) -> do BFS for evevry insertion
class CBTInserter {

    private TreeNode root;
    public CBTInserter(TreeNode root) {
        this.root = root;
    }
    
    public int insert(int val) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(this.root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.left == null) {
                cur.left = new TreeNode(val);
                return cur.val;
            } else if (cur.right == null) {
                cur.right = new TreeNode(val);
                return cur.val;
            } else {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        return -1;
    }
    
    public TreeNode get_root() {
        return this.root;
    }
}


 how to improve it? use another queue to record prarent node which has empty nodes
 -> make insertion to O(1)
 */