Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

919. Complete Binary Tree Inserter

Time: Constructor: $O(n)$, insert(v: int), get_root(): $O(1)$

Space: $O(n)$

			


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 & 1)
      parent->left = tree.back();
    else
      parent->right = tree.back();
    return parent->val;
  }

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

 private:
  vector<TreeNode*> tree;
};




			


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<>();
}




			


class CBTInserter:
  def __init__(self, root: Optional[TreeNode]):
    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 & 1:
      parent.left = self.tree[-1]
    else:
      parent.right = self.tree[-1]
    return parent.val

  def get_root(self) -> Optional[TreeNode]:
    return self.tree[0]