Else, insert as right child and remove the node from the queue (now full).
Add the new node to the queue (it may receive children in the future).
For get_root(), return the root node.
Code

[{"language":"C++","code":"class CBTInserter {\n    TreeNode* r;\n    std::queue<TreeNode*> q;\npublic:\n    CBTInserter(TreeNode* root) : r(root) {\n        std::queue<TreeNode*> t;\n        t.push(root);\n        while (!t.empty()) {\n            auto n = t.front(); t.pop();\n            if (!n->left || !n->right) q.push(n);\n            if (n->left) t.push(n->left);\n            if (n->right) t.push(n->right);\n        }\n    }\n    int insert(int v) {\n        auto n = q.front();\n        TreeNode* node = new TreeNode(v);\n        if (!n->left) n->left = node;\n        else { n->right = node; q.pop(); }\n        q.push(node);\n        return n->val;\n    }\n    TreeNode* get_root() { return r; }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> CBTInserter</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    TreeNode</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">*</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> r;</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    std</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">::queue</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">TreeNode</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">*></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> q;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    CBTInserter</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">TreeNode</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">*</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> root</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) : </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">r</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(root) {</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">        std</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">::queue</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">TreeNode</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">*></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> t;</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        t.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">push</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(root);</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        while</span><span style=\"c
Related Tags
