Complete Binary Tree Inserter LeetCode solution in C++

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 * int val;
5
 * TreeNode *left;
6
 * TreeNode *right;
7
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class CBTInserter {
14
 public:
15
  vector<TreeNode *> arr;
16

17
  CBTInserter(TreeNode *root) {
18
    arr.push_back(root);
19
    queue<TreeNode *> q;
20
    q.push(root);
21
    while (!q.empty()) {
22
      if (q.front()->left != NULL) {
23
        arr.push_back(q.front()->left);
24
        q.push(q.front()->left);
25
      }
26
      if (q.front()->right != NULL) {
27
        arr.push_back(q.front()->right);
28
        q.push(q.front()->right);
29
      }
30
      q.pop();
31
    }
32
  }
33

34
  int insert(int val) {
35
    TreeNode *new_node = new TreeNode(val);
36
    arr.push_back(new_node);
37
    int parent_index = (arr.size() - 2) / 2;
38
    if (2 * parent_index + 1 == arr.size() - 1) {
39
      arr[parent_index]->left = new_node;
40
    } else {
41
      arr[parent_index]->right = new_node;
42
    }
43
    return arr[parent_index]->val;
44
  }
45

46
  TreeNode *get_root() {
47
    return arr[0];
48
  }
49
};
50

51
/**
52
 * Your CBTInserter object will be instantiated and called as such:
53
 * CBTInserter* obj = new CBTInserter(root);
54
 * int param_1 = obj->insert(val);
55
 * TreeNode* param_2 = obj->get_root();
56
 */