919. Complete Binary Tree Inserter

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion.

Implement the CBTInserter class:

• CBTInserter(TreeNode root) Initializes the data structure with the root of the complete binary tree.
• int insert(int v) Inserts a TreeNode into the tree with value Node.val == val so that the tree remains complete, and returns the value of the parent of the inserted TreeNode.
• TreeNode get_root() Returns the root node of the tree.
   

Example 1:

Input:
[“CBTInserter”, “insert”, “insert”, “get_root”]
[[[1, 2]], [3], [4], []]
Output:
[null, 1, 2, [1, 2, 3, 4]]
Explanation
CBTInserter cBTInserter = new CBTInserter([1, 2]);
cBTInserter.insert(3); // return 1
cBTInserter.insert(4); // return 2
cBTInserter.get_root(); // return [1, 2, 3, 4]

Constraints:

• The number of nodes in the tree will be in the range [1, 1000].
• 0 <= Node.val <= 5000
• root is a complete binary tree.
• 0 <= val <= 5000
• At most 104 calls will be made to insert and get_root.

From: LeetCode
Link: 919. Complete Binary Tree Inserter

Solution:

Ideas:

• Key idea:

  • Keep a queue (cand) of nodes that can accept a new child (i.e., not having both left and right children).

• Initialization (cBTInserterCreate):

  • Perform a level-order traversal (BFS) from the root.
  • Add every node with at least one empty child into the candidate queue.

• Insert (cBTInserterInsert):

  • Take the front node of the queue (the current parent).
  • Insert the new node as its left child if empty; otherwise as right child.
  • If the parent now has both children, remove it from the queue.
  • Add the newly inserted node to the queue (it may receive children later).
  • Return the value of the parent node.

• Get root (cBTInserterGet_root):

  • Simply return the stored root pointer.

• Free (cBTInserterFree):

  • Free memory used by the candidate queue and the structure itself.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

typedef struct {
    struct TreeNode *root;
    struct TreeNode **cand;   // parents with at least one empty child
    int head, tail, cap;      // simple grow-only queue indices
} CBTInserter;

/* ------- internal helpers ------- */
static void ensure_capacity(CBTInserter *obj, int extra) {
    if (obj->tail + extra < obj->cap) return;
    while (obj->tail + extra >= obj->cap) obj->cap <<= 1;
    obj->cand = (struct TreeNode **)realloc(obj->cand, obj->cap * sizeof(struct TreeNode *));
}

static void enqueue(CBTInserter *obj, struct TreeNode *node) {
    ensure_capacity(obj, 1);
    obj->cand[obj->tail++] = node;
}

/* ------- API ------- */
CBTInserter* cBTInserterCreate(struct TreeNode* root) {
    CBTInserter *obj = (CBTInserter *)malloc(sizeof(CBTInserter));
    obj->root = root;
    obj->cap = 2048;                   // plenty; will grow if needed
    obj->cand = (struct TreeNode **)malloc(obj->cap * sizeof(struct TreeNode *));
    obj->head = obj->tail = 0;

    // Level-order traversal to find initial candidate parents
    int qcap = 2048;
    struct TreeNode **q = (struct TreeNode **)malloc(qcap * sizeof(struct TreeNode *));
    int h = 0, t = 0;
    q[t++] = root;

    while (h < t) {
        struct TreeNode *cur = q[h++];
        if (cur->left) {
            if (t >= qcap) { qcap <<= 1; q = (struct TreeNode **)realloc(q, qcap * sizeof(struct TreeNode *)); }
            q[t++] = cur->left;
        }
        if (cur->right) {
            if (t >= qcap) { qcap <<= 1; q = (struct TreeNode **)realloc(q, qcap * sizeof(struct TreeNode *)); }
            q[t++] = cur->right;
        }
        if (!(cur->left && cur->right)) enqueue(obj, cur);  // has a free child spot
    }
    free(q);
    return obj;
}

int cBTInserterInsert(CBTInserter* obj, int val) {
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;

    struct TreeNode *par = obj->cand[obj->head];
    if (par->left == NULL) {
        par->left = node;
    } else {
        par->right = node;
        obj->head++;                   // parent is now full
    }
    enqueue(obj, node);                // new node may accept children later
    return par->val;
}

struct TreeNode* cBTInserterGet_root(CBTInserter* obj) {
    return obj->root;
}

void cBTInserterFree(CBTInserter* obj) {
    if (!obj) return;
    free(obj->cand);
    free(obj);
}

/*
 * Your CBTInserter struct will be instantiated and called as such:
 * CBTInserter* obj = cBTInserterCreate(root);
 * int param_1 = cBTInserterInsert(obj, val);
 * struct TreeNode* param_2 = cBTInserterGet_root(obj);
 * cBTInserterFree(obj);
 */