Leetcode 919: Complete Binary Tree Inserter
You are given a complete binary tree. A complete binary tree is one where every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Your task is to design a data structure that supports inserting new nodes while maintaining the completeness of the binary tree. Implement the CBTInserter class that supports two operations: inserting a new node and returning the root of the tree.
Problem
Approach
Steps
Complexity
Input: You are given the root of a complete binary tree and a value to insert.
Example: Input: root = [1, 2], val = 3
Constraints:
• 1 <= n <= 1000
• 0 <= Node.val <= 5000
• 0 <= val <= 5000
• At most 10^4 calls to insert and get_root will be made.
Output: The `insert` method should return the value of the parent node of the newly inserted node. The `get_root` method should return the root node of the tree.
Example: Output: [null, 1, 2, [1, 2, 3, 4]]
Constraints:
• The tree will always remain complete after each insertion.
Goal: The goal is to maintain the completeness of the binary tree after each insertion while ensuring efficient updates.
Steps:
• Use a list (array) to store the nodes in level-order. This allows easy access to parent and child nodes for insertion.
• When inserting a new node, add it to the list and determine whether it should be the left or right child of its parent, based on the index of the new node.
• Update the tree structure in the list and return the parent node's value.
Goal: The tree will contain at least one node, and the values will be within the specified ranges.
Steps:
• The tree will contain between 1 and 1000 nodes.
• Each node's value and the value to be inserted will be between 0 and 5000.
• At most 10^4 operations will be performed.
Assumptions:
• The input binary tree is a complete binary tree before the first insertion.
• The new node will always be inserted in the next available spot in the tree to maintain completeness.
• Input: Input: root = [1, 2], val = 3
• Explanation: The tree before insertion is [1, 2]. After inserting 3, the new tree becomes [1, 2, 3], where 1 is the parent of 2 and 3. The return value is the parent node's value, which is 1.
• Input: Input: root = [1, 2, 3, 4], val = 5
• Explanation: Before the insertion, the tree is [1, 2, 3, 4]. After inserting 5, the tree becomes [1, 2, 3, 4, 5]. The parent node of 5 is 2, so the return value is 2.
Approach: To insert a new node into the complete binary tree while maintaining its completeness, we use an array-based approach to store the tree in level order. This allows efficient access to parent nodes and insertion points.
Observations:
• The tree is complete, so every insertion can be handled by simply adding the new node to the next available position in the tree.
• Using a list to represent the tree in level order allows us to efficiently manage the insertions and get the parent of the inserted node in constant time.
Steps:
• Step 1: Store the root of the tree in an array `tree` to keep track of the nodes in level order.
• Step 2: For each insertion, append the new node to the array and determine its parent by checking whether its index is odd or even.
• Step 3: Update the parent-child relationship based on the calculated index and return the parent's value.
Empty Inputs:
• The problem guarantees that the tree will have at least one node, so there will be no empty inputs.
Large Inputs:
• The algorithm should handle up to 10^4 insertions efficiently.
Special Values:
• If the tree has only one node, the next insertion should simply add the second node as the left child.
Constraints:
• The tree will remain complete at all times, so there is no need to rebalance it.
* 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 {
vector<TreeNode*> tree;
public:
CBTInserter(TreeNode* root) {
tree.push_back(root);
for(int i = 0; i < tree.size(); i++) {
if(tree[i]->left) tree.push_back(tree[i]->left);
if(tree[i]->right) tree.push_back(tree[i]->right);
}
}
int insert(int val) {
int N = tree.size();
TreeNode* node = new TreeNode(val);
tree.push_back(node);
if(N%2) tree[(N-1)/2]->left = node;
else tree[(N-1)/2]->right= node;
return tree[(N-1)/2]->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();
1 : Class Declaration
class CBTInserter {
Define the 'CBTInserter' class that manages a complete binary tree and provides methods for insertion and retrieval.
2 : Variable Declaration
vector<TreeNode*> tree;
A vector of pointers to 'TreeNode' objects, which holds the nodes of the complete binary tree.
3 : Access Specifier
public:
Specifies that the following methods and members are publicly accessible.
4 : Constructor
CBTInserter(TreeNode* root) {
Constructor for the 'CBTInserter' class that initializes the tree with the root node.
5 : Tree Initialization
tree.push_back(root);
Add the root node to the 'tree' vector.
6 : Loop
for(int i = 0; i < tree.size(); i++) {
Start a loop to traverse all nodes in the tree and add their children to the 'tree' vector.
7 : Child Insertion
if(tree[i]->left) tree.push_back(tree[i]->left);
If the current node has a left child, add it to the 'tree' vector.
8 : Child Insertion
if(tree[i]->right) tree.push_back(tree[i]->right);
If the current node has a right child, add it to the 'tree' vector.
9 : Method
int insert(int val) {
Define the 'insert' method that inserts a new node with value 'val' into the tree.
10 : Variable Declaration
int N = tree.size();
Store the current size of the 'tree' vector, which is used to find the parent node of the new node.
11 : Node Creation
TreeNode* node = new TreeNode(val);
Create a new 'TreeNode' with the given value 'val'.
12 : Tree Update
tree.push_back(node);
Add the newly created node to the 'tree' vector.
13 : Child Assignment
if(N%2) tree[(N-1)/2]->left = node;
If 'N' is odd, assign the new node as the left child of its parent.
14 : Child Assignment
else tree[(N-1)/2]->right= node;
If 'N' is even, assign the new node as the right child of its parent.
15 : Return Statement
return tree[(N-1)/2]->val;
Return the value of the parent node to confirm where the new node was inserted.
16 : Method
TreeNode* get_root() {
Define the 'get_root' method that returns the root of the tree.
17 : Return Statement
return tree[0];
Return the root of the tree (the first element in the 'tree' vector).
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: Both the `insert` and `get_root` operations run in constant time O(1), as we are only adding a new node to the list and returning the root.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n), where n is the number of nodes in the tree, as we store all nodes in the list.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus