Sponsored
Sponsored
The idea is to use a queue to track the nodes at the current level and help find where to insert a new node to maintain the complete binary tree property.
When inserting, always maintain a queue that holds nodes which can potentially have children added to them. Initially, populate the queue with nodes from the complete tree using level-order traversal where a node is added only if it can further accommodate more children.
For each insertion, take the node from the front of the queue and insert the new child. If a node has both children filled after insertion, remove it from the queue. New nodes always get added to the end of the queue to maintain the complete binary tree property.
Both the insertion and retrieving the root operations run with O(1) time complexity. The space complexity is O(n) for storing nodes in the deque.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class CBTInserter:
10 def __init__(self, root: TreeNode):
11 self.root = root
12 self.deque = deque()
13 queue = deque([root])
14 while queue:
15 node = queue.popleft()
16 if not node.left or not node.right:
17 self.deque.append(node)
18 if node.left:
19 queue.append(node.left)
20 if node.right:
21 queue.append(node.right)
22
23 def insert(self, v: int) -> int:
24 parent = self.deque[0]
25 new_node = TreeNode(v)
26 if not parent.left:
27 parent.left = new_node
28 else:
29 parent.right = new_node
30 self.deque.popleft()
31 self.deque.append(new_node)
32 return parent.val
33
34 def get_root(self) -> TreeNode:
35 return self.rootWe initialize the class by performing a level-order traversal of the tree to add each node to a queue if it can have children nodes added.
During insertion, we check the first node in our queue for having a room for a new child (left or right). We insert the new node, if both children nodes are filled, then we remove the parent from the queue as it's full and add the newly inserted node to maintain order.
Time complexity for initializing the class constructor is O(n) and for insert operation is O(1).
This approach still employs a level order traversal starting from the root for every insertion to find the first available spot, thus maintaining the complete binary tree properties.
With each insertion, traverse the tree using a queue to ensure for each node, you check if it is either missing a left or right child. Stop and insert the new node at the first possible position found.
Even though this method is less efficient during each insert because of repeated traversal, it effectively maintains tree completeness by directly probing the current state of the tree.
For the `insert` method, the time complexity per insertion operation can reach O(n) in the worst case if re-traversing the tree is required. The `get_root` call is O(1).
Space complexity is O(n) for managing the additional queue during the insertion process.
1import java.util.LinkedList
In this Java solution, for every insert call, we perform a level order traversal from the root node to find where the new value should go. A standard queue supports the traversal to ensure the completeness property of the binary tree.
The get_root operation directly returns the stored root. This approach can be less optimal than using a persistent queue but systematically searches for the next possible insertion point.