Leetcode 919. Complete Binary Tree Inserter

Problem Explanation: The problem is asking us to create two operations a constructor and two methods that insert a node into the binary tree and get the root node. CBTInserter is a constructor which takes the root of the complete binary tree as an argument. To maintain the complete binary property of the tree, each new node is inserted to the right-most vacant place in the last level if it exists. If the last level was occupied fully, the node is added as the left child of the first node in the next level. Insert method takes an integer as an argument, and the return is the value of the parent of that node which we just inserted. get_root method returns the root of the tree.

Example: Consider an input series of operations ["CBTInserter","insert","insert","get_root"] with corresponding inputs [[[1,2,3,4,5,6]],[7],[8],[]]. The starting tree is [1,2,3,4,5,6] which looks like this:

1    1
2  /   \
3 2     3

/ \ / 4 5 6

First, insert(7) operation is performed. 7 is inserted as the right child of 6, and the return value is 6. The updated tree looks like below:

1    1
2  /   \
3 2     3

/ \ /
4 5 6 7

Then, insert(8) operation is performed. As the last level of the tree is filled completely, 8 is inserted as the left child of 2 (first node of the new last level), and the return value is 2. The final tree looks like below:

1    1
2  /   \
3 2     3

/ \ /
8 5 6 7 / 4

Finally, get_root operation is performed which returns the whole tree [1,2,3,4,5,6,7,8] in list format.

The solution approach is following a Breadth-First Search (BFS) style algorithm. Since new nodes in complete binary trees are inserted level by level from left to right, we can maintain a list tree which stores all the nodes of the current tree in a BFS order. The parent of the node to be inserted next will always be tree[(tree.size() - 1) / 2].

Python Solution:

1
2python
3from collections import deque
4class CBTInserter:
5    def __init__(self, root):
6        self.deque = deque()
7        self.root = root
8        q = deque([root])
9        while q:
10            node = q.popleft()
11            if not node.left or not node.right:
12                self.deque.append(node)
13            if node.left:
14                q.append(node.left)
15            if node.right:
16                q.append(node.right)
17                
18    def insert(self, v):
19        node = TreeNode(v)
20        parent = self.deque[0]
21        if not parent.left:
22            parent.left = node
23        else:
24            parent.right = node
25            self.deque.popleft()
26        self.deque.append(node)
27        return parent.val
28
29    def get_root(self):
30        return self.root

Java Solution:

1
2java
3class CBTInserter {
4    private List<TreeNode> tree;
5
6    public CBTInserter(TreeNode root) {
7        tree = new ArrayList<>();
8        tree.add(root);
9        for (int i = 0; i < tree.size(); ++i) {
10            TreeNode node = tree.get(i);
11            if (node.left != null)
12                tree.add(node.left);
13            if (node.right != null)
14                tree.add(node.right);
15        }
16    }
17
18    public int insert(int v) {
19        TreeNode node = new TreeNode(v);
20        int N = tree.size();
21        tree.add(node);
22        if (N % 2==1)
23            tree.get((N - 1) / 2).left = node;
24        else
25            tree.get((N - 1) / 2).right = node;
26        return tree.get((N - 1) / 2).val;
27    }
28
29    public TreeNode get_root() {
30        return tree.get(0);
31    }
32}

JavaScript Solution:

1
2js
3class CBTInserter {
4    constructor(root) {
5        this.tree = [root];
6        for (let i = 0; i < this.tree.length; ++i) {
7            let node = this.tree[i];
8            if (node.left) this.tree.push(node.left);
9            if (node.right) this.tree.push(node.right);
10        }
11    }
12    
13    insert(v) {
14        let node = new TreeNode(v);
15        let N = this.tree.length;
16        this.tree.push(node);
17        if (N % 2 == 1) this.tree[(N - 1) / 2].left = node;
18        else this.tree[(N - 1) / 2].right = node;
19        
20        return this.tree[(N - 1) / 2].val;
21    }
22    
23    get_root() {
24        return this.tree[0];
25    }
26}
27

C++ Solution:

1
2cpp
3class CBTInserter {
4 public:
5    CBTInserter(TreeNode* root) {
6        tree.push_back(root);
7        for (int i = 0; i < tree.size(); ++i) {
8            if (tree[i]->left)
9                tree.push_back(tree[i]->left);
10            if (tree[i]->right)
11                tree.push_back(tree[i]->right);
12        }
13    }
14
15    int insert(int v) {
16        int N = tree.size();
17        TreeNode* node = new TreeNode(v);
18        tree.push_back(node);
19        if (N % 2)
20            tree[(N - 1)/2]->left = node;
21        else
22            tree[(N - 1)/2]->right = node;
23        return tree[(N - 1)/2]->val;
24    }
25
26    TreeNode* get_root() {
27        return tree[0];
28    }
29 private:
30  vector<TreeNode*> tree;
31};

In the given examples, we used BFS approach which is resulted in an efficient solution for the problem. This approach works by traversing and processing the tree one level at a time, starting from the left.

In Python, we utilise the collections library which provides high-performance container datatypes, like deque. Deque is preferred over lists in the cases where we need quick append and pop operations from both the ends of container.

In Java, ArrayList is used for storing tree nodes. The ArrayList class extends AbstractList and implements the List interface. ArrayList supports dynamic arrays that can grow as needed which is required for this problem.

JavaScript follows similar approach as Java and Python by pushing nodes onto a tree array and placing the new nodes in the appropriate position according to their values.

In C++, we use vector to store the nodes of the tree. Vector in C++ STL is a dynamic array that implements data structure that can be expanded or contracted as needed.

This BFS-based approach ensures we always insert the next new node at the earliest viable spot to maintain the complete binary tree property. This way, we satisfy the requirement of adding a node to the right-most vacant place in the last level if it exists, or as the left child of the first node in the next level.

In conclusion, in order to maintain the complete binary tree, you need to track all nodes in the tree using BFS traversal. Store the nodes in a container and for the node to be inserted next, calculate the parent by using the formula parent = tree[(tree.size() - 1) / 2]. If the parent node doesn't have a left child, add the new node as the left child. If it has a left child already, add the new node as the right child and move to the next parent node in the container. This approach takes O(1) time complexity for both inserts and get_root operations with the memory footprint proportional to the number of nodes in the tree.