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.
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8} TreeNode;
9
10typedef struct CBTInserter {
11 TreeNode *root;
12 TreeNode **queue;
13 int front;
14 int rear;
15 int size;
16 int capacity;
17} CBTInserter;
18
19TreeNode* createNode(int val) {
20 TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
21 node->val = val;
22 node->left = node->right = NULL;
23 return node;
24}
25
26CBTInserter* cBTInserterCreate(TreeNode* root) {
27 CBTInserter* obj = (CBTInserter*)malloc(sizeof(CBTInserter));
28 obj->root = root;
29 obj->front = 0;
30 obj->rear = 0;
31 obj->capacity = 1000;
32 obj->queue = (TreeNode**)malloc(sizeof(TreeNode*) * obj->capacity);
33
34 TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * obj->capacity);
35 int head = 0, tail = 0;
36 queue[tail++] = root;
37
38 while (head < tail) {
39 TreeNode* node = queue[head++];
40 if (node->left) queue[tail++] = node->left;
41 if (node->right) queue[tail++] = node->right;
42
43 if (!node->left || !node->right) {
44 obj->queue[obj->rear++] = node;
45 }
46 }
47
48 free(queue);
49 return obj;
50}
51
52int cBTInserterInsert(CBTInserter* obj, int v) {
53 TreeNode *parent = obj->queue[obj->front];
54 TreeNode *newNode = createNode(v);
55 if (!parent->left) {
56 parent->left = newNode;
57 } else {
58 parent->right = newNode;
59 obj->front++;
60 }
61 obj->queue[obj->rear++] = newNode;
62 return parent->val;
63}
64
65TreeNode* cBTInserterGet_root(CBTInserter* obj) {
66 return obj->root;
67}
68
69void cBTInserterFree(CBTInserter* obj) {
70 free(obj->queue);
71 free(obj);
72}This solution uses a manual management of a queue of node pointers to simulate a level-order traversal in C, a language without built-in queue support. We initialize the CBTInserter with available slots for children from a breadth-first traversal. During each insert operation, we add the new node as a left or right child.
Time complexity for initial loading in the constructor is O(n) through node population, while the insertion operation takes O(1) for its placement.
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.
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.