# 919. 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.

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.

**Example 1:**![](https://assets.leetcode.com/uploads/2021/08/03/lc-treeinsert.jpg)

```
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]
```

**Constraints:**

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

## Solution

Have no idea.

The key is to realize the relationship between the adding node and it parents.

![](https://2628390332-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M0RnkuvOeqe0clAIN1b%2F-MjwBy2Nf8EXn04fiqfx%2F-MjwSWzbs1XyQUBaO0lK%2Fimage.png?alt=media\&token=71f13017-72d1-4641-87c5-71e0f0a665c9)

Then the next mission is to classify the tree into a structure that we can easily access any node with index we want. We choose to use a list as the Data structure. And by BFS to classify the tree.

```java
class CBTInserter {
    List<TreeNode> nodes;
    public CBTInserter(TreeNode root) {
        nodes = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            nodes.add(node);
            if(node.left != null){ 
                q.add(node.left);
            }
            if(node.right != null){
                q.add(node.right);
            }
        }
    }
    
    public int insert(int val) {
        int n = nodes.size();
        TreeNode node = new TreeNode(val);
        if((n-1)%2 == 0) {
            nodes.get((n-1)/2).left = node;
        }else{
            nodes.get((n-1)/2).right = node;
        }
        nodes.add(node);
        return nodes.get((n-1)/2).val;
    }
    
    public TreeNode get_root() {
        return nodes.get(0);   
    }
}
```
