---
tags: leetcode
---

# [919. Complete Binary Tree Inserter](https://leetcode.com/problems/complete-binary-tree-inserter/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

/**
 * Definition for a binary tree node.
 * 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 {
public:
    CBTInserter(TreeNode *root) : root(root) {
        bfs(root);
    }

    int insert(int val) {
        TreeNode *newNode = new TreeNode(val);
        TreeNode *node = nodeQ.front();

        if (node->left == nullptr) {
            node->left = newNode;
            nodeQ.push(newNode);
            return node->val;
        }

        node->right = newNode;
        nodeQ.pop();
        nodeQ.push(newNode);
        return node->val;
    }

    TreeNode *get_root() {
        return root;
    }
private:
    queue<TreeNode *> nodeQ;
    TreeNode *root;

    void bfs(TreeNode *root) {
        queue<TreeNode *> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode *curr = q.front();
            q.pop();

            if (curr->right == nullptr) {
                nodeQ.push(curr);
            }

            if (curr->left != nullptr) {
                q.push(curr->left);
            }
            if (curr->right != nullptr) {
                q.push(curr->right);
            }
        }
    }
};

/**
 * 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();
 */

## Time Complexity
* `CBTInserter`
$O(n)$
$n$ is the number of nodes in the complete binary tree referred by `root`.
* `insert`
$O(1)$
* `get_root`
$O(1)$
## Space Complexity
* `CBTInserter`
$O(n)$
* `insert`
$O(1)$
* `get_root`
$O(1)$
# Miscellaneous
<!--
# Test Cases

["CBTInserter","insert","insert","get_root"]
[[[1,2]],[3],[4],[]]

["CBTInserter","insert","get_root"]
[[[1]],[2],[]]

["CBTInserter","insert","insert","get_root"]
[[[1,2,3,4,5,6]],[7],[8],[]]

["CBTInserter","insert","insert","insert","get_root"]
[[[1]],[2],[3],[4],[]]

["CBTInserter","insert","insert","insert","insert","insert","get_root"]
[[[1]],[2],[3],[4],[5],[6],[]]

-->