# Complete Binary Tree Inserter
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/complete-binary-tree-inserter)
Canonical: https://scaleengineer.com/dsa/problems/complete-binary-tree-inserter
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
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.glich.co/dsa/complete-binary-tree-inserter/image0.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`.

# Approaches
## Brute-Force: Level-Order Traversal on Each Insertion
This approach involves finding the correct insertion point for each new node by traversing the tree from the root every time `insert` is called. A complete binary tree requires the new node to be placed at the first available position from the left in the lowest level. This position can be found using a Breadth-First Search (BFS), also known as a level-order traversal.
**Time:** `CBTInserter`: O(1)
`insert`: O(N), where N is the number of nodes in the tree. In the worst case, we traverse all N nodes to find the insertion point.
`get_root`: O(1) · **Space:** O(W), where W is the maximum width of the tree. For a complete binary tree, W can be up to (N+1)/2, making the space complexity O(N). This space is used by the queue during the BFS traversal in the `insert` method.
**Pros:** Simple to understand and implement.; It does not require any extra persistent data structures besides the tree itself.
**Cons:** The `insert` operation is inefficient with a time complexity of O(N).; For a large number of `insert` calls, this approach can be very slow as it repeatedly traverses a growing tree from the root.
### Explanation
The constructor, `CBTInserter(root)`, simply stores a reference to the root of the tree, which is an O(1) operation. The main logic resides in the `insert(val)` method. For each call to `insert`, we perform a full level-order traversal starting from the root. We use a queue to manage the nodes to visit. We explore the tree level by level, from left to right. The first time we encounter a node that has a `null` left child, we place the new node there. If the left child is already present, we check the right child. If the right child is `null`, we insert the new node there. If both children are present, we add both children to the queue and continue the search. This process guarantees that we find the first available spot as required for a complete binary tree, but it requires re-scanning a significant portion of the tree for every single insertion.

```java
/**
 * 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 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 node = queue.poll();

            if (node.left == null) {
                node.left = new TreeNode(val);
                return node.val;
            } else {
                queue.offer(node.left);
            }

            if (node.right == null) {
                node.right = new TreeNode(val);
                return node.val;
            } else {
                queue.offer(node.right);
            }
        }
        return -1; // Should not be reached given the problem constraints
    }

    public TreeNode get_root() {
        return this.root;
    }
}
```
### Algorithm
*   **`CBTInserter(root)`:**
    *   Store the `root` node in a member variable.
*   **`insert(val)`:**
    1.  Initialize a queue for Breadth-First Search (BFS) and add the `root` to it.
    2.  Start a loop that continues as long as the queue is not empty.
    3.  In each iteration, dequeue a node, let's call it `current`.
    4.  Check if `current.left` is `null`. If it is, this is the first available spot. Create a new `TreeNode` with `val`, set it as `current.left`, and return `current.val`.
    5.  If `current.left` is not `null`, add it to the queue to visit its children later.
    6.  Check if `current.right` is `null`. If it is, this is the next available spot. Create the new node, set it as `current.right`, and return `current.val`.
    7.  If `current.right` is not `null`, add it to the queue.
*   **`get_root()`:**
    *   Return the stored `root` node.

## Optimized Approach using a Queue of Parent Nodes
To avoid re-traversing the tree on every insertion, we can pre-process the tree and maintain a data structure that gives us direct access to the nodes that are available to be parents. In a complete binary tree, new nodes are added to the left-most available spot. The parents of these new nodes will be the first nodes in a level-order traversal that are not "full" (i.e., have fewer than two children). We can use a queue to store these potential parent nodes, allowing for O(1) insertions.
**Time:** `CBTInserter`: O(N), for the initial BFS to populate the `candidates` queue.
`insert`: O(1). All queue operations (peek, offer, poll) are constant time.
`get_root`: O(1). · **Space:** O(W), where W is the maximum width of the tree. The `candidates` queue stores non-full nodes, which are located in the last and second-to-last levels. The number of nodes in these levels is at most `(N+1)/2 + (N+1)/4`, so the space complexity is O(N).
**Pros:** Extremely efficient `insert` operation with O(1) time complexity.; The one-time setup cost in the constructor is amortized over all subsequent `insert` calls, making it ideal for scenarios with many insertions.
**Cons:** Requires additional space for the queue of candidate parent nodes.; The constructor has a one-time setup cost of O(N) in both time and space.
### Explanation
This optimized approach trades a one-time setup cost for highly efficient insertions. 

In the constructor `CBTInserter(root)`, we perform a single BFS traversal over the entire initial tree. The purpose of this traversal is to find all nodes that are not yet full (i.e., have at least one `null` child pointer). We add these nodes to a dedicated queue, which we'll call `candidates`. Because we find them via BFS, they are naturally ordered by level, from left to right. The node at the front of this `candidates` queue is precisely the parent where the next insertion must occur.

When `insert(val)` is called, we don't need to search the tree. We simply `peek()` at the `candidates` queue to get the parent node. We create the new node and attach it to the parent's first available child slot (left, then right). The new node itself is now a candidate for being a parent, so we add it to the `candidates` queue. If attaching the new node made the parent node full (i.e., we filled its right child slot), we `poll()` the parent from the `candidates` queue. This entire process involves a few simple queue operations, making it O(1).

```java
/**
 * 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 TreeNode root;
    private Queue<TreeNode> candidates;

    public CBTInserter(TreeNode root) {
        this.root = root;
        this.candidates = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left == null || node.right == null) {
                this.candidates.offer(node);
            }
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null) {
                q.offer(node.right);
            }
        }
    }

    public int insert(int val) {
        TreeNode parent = this.candidates.peek();
        TreeNode newNode = new TreeNode(val);
        this.candidates.offer(newNode);

        if (parent.left == null) {
            parent.left = newNode;
        } else { // parent.right must be null
            parent.right = newNode;
            this.candidates.poll(); // This parent is now full, remove it
        }
        return parent.val;
    }

    public TreeNode get_root() {
        return this.root;
    }
}
```
### Algorithm
*   **`CBTInserter(root)`:**
    1.  Initialize a queue, `candidates`, to store nodes that can accept new children.
    2.  Store the `root` in a member variable.
    3.  Perform a one-time level-order traversal (BFS) of the initial tree.
    4.  During the traversal, for each node visited, if it has fewer than two children (`node.left == null` or `node.right == null`), add it to the `candidates` queue.
*   **`insert(val)`:**
    1.  Get the parent for the new node by peeking at the front of the `candidates` queue (`parent = candidates.peek()`).
    2.  Create the new node, `newNode`, with the given value `val`.
    3.  Add `newNode` to the back of the `candidates` queue, as it's a potential parent for future insertions.
    4.  If `parent.left` is `null`, attach `newNode` as the left child.
    5.  Otherwise, `parent.right` must be `null`. Attach `newNode` as the right child. Since this makes the `parent` node full, remove it from the front of the `candidates` queue.
    6.  Return `parent.val`.
*   **`get_root()`:**
    *   Return the stored `root` node.

# Solutions
### Java

```java
/** * 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 List < TreeNode > tree ; public CBTInserter ( TreeNode root ) { tree = new ArrayList <>(); Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { TreeNode node = q . pollFirst (); tree . add ( node ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } public int insert ( int val ) { int pid = ( tree . size () - 1 ) >> 1 ; TreeNode node = new TreeNode ( val ); tree . add ( node ); TreeNode p = tree . get ( pid ); if ( p . left == null ) { p . left = node ; } else { p . right = node ; } return p . val ; } public TreeNode get_root () { return tree . get ( 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(); */
```

### JavaScript

```javascript
/** * 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 . tree = []; const q = [ root ]; while ( q . length ) { const node = q . shift (); this . tree . push ( node ); if ( node . left ) { q . push ( node . left ); } if ( node . right ) { q . push ( node . right ); } } }; /** * @param {number} val * @return {number} */ CBTInserter . prototype . insert = function ( val ) { const pid = ( this . tree . length - 1 ) >> 1 ; const node = new TreeNode ( val ); this . tree . push ( node ); const p = this . tree [ pid ]; if ( ! p . left ) { p . left = node ; } else { p . right = node ; } return p . val ; }; /** * @return {TreeNode} */ CBTInserter . prototype . get_root = function () { return this . tree [ 0 ]; }; /** * 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() */
```

### CPP

```cpp
/** * 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 *> tree ; CBTInserter ( TreeNode * root ) { queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { auto node = q . front (); q . pop (); tree . push_back ( node ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } } int insert ( int val ) { int pid = tree . size () - 1 >> 1 ; TreeNode * node = new TreeNode ( val ); tree . push_back ( node ); TreeNode * p = tree [ pid ]; if ( ! p -> left ) p -> left = node ; else p -> right = node ; return p -> val ; } TreeNode * get_root () { return tree [ 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(); */
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class CBTInserter : def __init__ ( self , root : TreeNode ): self . tree = [] q = deque ([ root ]) while q : for _ in range ( len ( q )): node = q . popleft () self . tree . append ( node ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) def insert ( self , val : int ) -> int : pid = ( len ( self . tree ) - 1 ) >> 1 node = TreeNode ( val ) self . tree . append ( node ) p = self . tree [ pid ] if p . left is None : p . left = node else : p . right = node return p . val def get_root ( self ) -> TreeNode : return self . tree [ 0 ] # Your CBTInserter object will be instantiated and called as such: # obj = CBTInserter(root) # param_1 = obj.insert(val) # param_2 = obj.get_root()
```