Complete Binary Tree Inserter

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.

Write a data structure CBTInserter that is initialized with a complete binary tree and supports the following operations:

CBTInserter(TreeNode root) initializes the data structure on a given tree with head node root;
CBTInserter.insert(int v) will insert a TreeNode into the tree with value node.val = v so that the tree remains complete, and returns the value of the parent of the inserted TreeNode;
CBTInserter.get_root() will return the head node of the tree.

Example 1:

Input: inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
Output: [null,1,[1,2]]

Example 2:

Input: inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
Output: [null,3,4,[1,2,3,4,5,6,7,8]]

Note:

The initial given tree is complete and contains between 1 and 1000 nodes.
CBTInserter.insert is called at most 10000 times per test case.
Every value of a given or inserted node is between 0 and 5000.

Solution:

/**
 * 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 {
    TreeNode root;
    Deque<TreeNode> queue;    

    public CBTInserter(TreeNode root) {
        this.root = root;
        queue = new ArrayDeque();
        queue.offer(root);
        while (true) {
            TreeNode curr = queue.peek();
            int size = queue.size();
            if (curr.left != null && curr.right != null) {
                queue.poll();
                queue.offer(curr.left);
                queue.offer(curr.right);
            } else if (curr.left != null) {
                queue.offer(curr.left);
                break;
            }
            if (size == queue.size()) break;
        }
    }
    
    public int insert(int v) {
        TreeNode insertParent = queue.peek();
        int ret = insertParent.val;
        TreeNode node = new TreeNode(v);
        if (insertParent.left == null) {
            insertParent.left = node;
        } else {
            insertParent.right = node;
            queue.poll();
        }
        queue.offer(node);
        // System.out.println(queue);
        return ret;
    }
    
    public TreeNode get_root() {
        return root;
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */