Skip to content

919. Complete Binary Tree Inserter 👍

  • Time: Constructor: $O(n)$, insert(v: int), get_root(): $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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]