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:
<li><code>CBTInserter(TreeNode root)</code> initializes the data structure on a given tree with head node <code>root</code>;</li>
<li><code>CBTInserter.insert(int v)</code> will insert a <code>TreeNode</code> into the tree with value <code>node.val = v</code> so that the tree remains complete, <strong>and returns the value of the parent of the inserted <code>TreeNode</code></strong>;</li>
<li><code>CBTInserter.get_root()</code> will return the head node of the tree.</li>
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:
<li>The initial given tree is complete and contains between <code>1</code> and <code>1000</code> nodes.</li>
<li><code>CBTInserter.insert</code> is called at most <code>10000</code> times per test case.</li>
<li>Every value of a given or inserted node is between <code>0</code> and <code>5000</code>.</li>