Similar Problems
Similar Problems not available
Complete Binary Tree Inserter  Leetcode Solution
LeetCode: Complete Binary Tree Inserter Leetcode Solution
Difficulty: Medium
Topics: design tree binarytree breadthfirstsearch
The Complete Binary Tree Inserter problem on leetcode requires you to implement a class that can insert nodes into a complete binary tree. A complete binary tree is one where every level except the last is completely filled, and all nodes are as far left as possible. Here are the steps to solve this problem:

Create a class called
CBTInserter
that takes in the root of a complete binary tree as its constructor argument. 
In the constructor, traverse the tree level by level and store all the nodes in a list or queue. You can use breadthfirst search to traverse the tree level by level.

Implement the
insert
method that takes in an integer valuev
and inserts it as a new node into the complete binary tree. To do this, append a new node with the given value to the end of the list of nodes. Calculate the index of the parent node for the new node using integer division and subtracting 1 from the index to account for 0based indexing. Then set the parent of the new node as the node at the calculated parent index. 
Implement the
get_root
method that returns the root of the complete binary tree.
Here's the full implementation of the CBTInserter
class:
class CBTInserter:
def __init__(self, root: TreeNode):
self.nodes = []
# breadthfirst search to traverse the tree level by level
queue = [root]
while queue:
node = queue.pop(0)
if node:
self.nodes.append(node)
queue.append(node.left)
queue.append(node.right)
def insert(self, v: int) > int:
node = TreeNode(v)
self.nodes.append(node)
parent_index = (len(self.nodes)  2) // 2
parent = self.nodes[parent_index]
if not parent.left:
parent.left = node
else:
parent.right = node
return parent.val
def get_root(self) > TreeNode:
return self.nodes[0]
Note that in the insert
method, we return the value of the parent node, not the newly inserted node. This is because the problem statement only requires us to return the value of the parent node, not the node itself.
Overall, the time complexity of this implementation is O(log N) for insertions and O(1) for get_root, where N is the number of nodes in the tree. The space complexity is O(N) for storing all the nodes in the list.
Complete Binary Tree Inserter Solution Code
1