919. Complete Binary Tree Inserter LeetCode Solution

In this guide, you will get 919. Complete Binary Tree Inserter LeetCode Solution with the best time and space complexity. The solution to Complete Binary Tree Inserter problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Complete Binary Tree Inserter solution in C++
Complete Binary Tree Inserter solution in Java
Complete Binary Tree Inserter solution in Python
Additional Resources

919. Complete Binary Tree Inserter LeetCode Solution image

Problem Statement of Complete Binary Tree Inserter

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.
Implement the CBTInserter class:

CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree.
int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode.
TreeNode get_root() Returns the root node of the tree.

Example 1:

Input
[“CBTInserter”, “insert”, “insert”, “get_root”]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

Explanation
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); // return 1
cBTInserter.insert(4); // return 2
cBTInserter.get_root(); // return [1, 2, 3, 4]

Constraints:

The number of nodes in the tree will be in the range [1, 1000].
0 <= Node.val <= 5000
root is a complete binary tree.
0 <= val <= 5000
At most 104 calls will be made to insert and get_root.

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(n)

919. Complete Binary Tree Inserter LeetCode Solution in C++

class CBTInserter {
 public:
  CBTInserter(TreeNode* root) {
    tree.push_back(root);
    for (int i = 0; i < tree.size(); ++i) {
      TreeNode* node = tree[i];
      if (node->left)
        tree.push_back(node->left);
      if (node->right)
        tree.push_back(node->right);
    }
  }

  int insert(int v) {
    const int n = tree.size();
    tree.push_back(new TreeNode(v));
    auto& parent = tree[(n - 1) / 2];
    if (n % 2 == 1)
      parent->left = tree.back();
    else
      parent->right = tree.back();
    return parent->val;
  }

  TreeNode* get_root() {
    return tree[0];
  }

 private:
  vector<TreeNode*> tree;
};
/* code provided by PROGIEZ */

919. Complete Binary Tree Inserter LeetCode Solution in Java

class CBTInserter {
  public CBTInserter(TreeNode root) {
    tree.add(root);
    for (int i = 0; i < tree.size(); ++i) {
      TreeNode node = tree.get(i);
      if (node.left != null)
        tree.add(node.left);
      if (node.right != null)
        tree.add(node.right);
    }
  }

  public int insert(int v) {
    final int n = tree.size();
    TreeNode node = new TreeNode(v);
    TreeNode parent = tree.get((n - 1) / 2);
    tree.add(node);
    if (n % 2 == 1)
      parent.left = node;
    else
      parent.right = node;
    return parent.val;
  }

  public TreeNode get_root() {
    return tree.get(0);
  }

  private List<TreeNode> tree = new ArrayList<>();
}
// code provided by PROGIEZ

919. Complete Binary Tree Inserter LeetCode Solution in Python

class CBTInserter:
  def __init__(self, root: TreeNode | None):
    self.tree = [root]
    for node in self.tree:
      if node.left:
        self.tree.append(node.left)
      if node.right:
        self.tree.append(node.right)

  def insert(self, v: int) -> int:
    n = len(self.tree)
    self.tree.append(TreeNode(v))
    parent = self.tree[(n - 1) // 2]
    if n % 2 == 1:
      parent.left = self.tree[-1]
    else:
      parent.right = self.tree[-1]
    return parent.val

  def get_root(self) -> TreeNode | None:
    return self.tree[0]
 # code by PROGIEZ