Complete Binary Tree Inserter - Practice Coding Problems

Complete Binary Tree Inserter - Problem

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.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["CBTInserter", "insert", "insert"], values = [[1], [2], [3]]

› Output: [null, 1, 1]

💡 Note: Initialize with tree [1]. Insert 2 as left child of 1 (return 1). Insert 3 as right child of 1 (return 1).

Example 2 — Multi-level Tree

$ Input: operations = ["CBTInserter", "insert", "insert", "insert"], values = [[1, 2], [3], [4], [5]]

› Output: [null, 1, 2, 2]

💡 Note: Start with [1,2]. Insert 3 as right child of 1. Insert 4 as left child of 2. Insert 5 as right child of 2.

Example 3 — Complete Tree Growth

$ Input: operations = ["CBTInserter", "insert", "insert", "get_root"], values = [[1, 2, 3, 4], [5], [6], []]

› Output: [null, 2, 2, [tree]]

💡 Note: Tree [1,2,3,4]. Insert 5 as right child of 2. Insert 6 as left child of 3. Tree grows level by level.

Constraints

1 ≤ operations.length ≤ 1000
1 ≤ val ≤ 100
The given tree is always a complete binary tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Initial complete binary tree with some nodes

Insert Process

Add nodes level by level, left to right

Complete Tree

Resulting tree maintains complete property

Key Takeaway

🎯 Key Insight: Pre-maintain a queue of nodes with available children for O(1) insertions

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is to maintain a queue of candidate nodes (nodes with available children slots) to achieve O(1) insertion time. The optimal approach uses BFS to pre-build this candidate queue during initialization. Time: O(1) per insert, Space: O(n) for candidate storage.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Level Order Search	O(n)	O(w)	For each insertion, traverse the entire tree to find insertion point
Optimized BFS with Candidate Queue	O(1)	O(n)	Maintain a queue of nodes that can accept new children

Brute Force - Level Order Search — Algorithm Steps

Step 1: Perform BFS traversal from root
Step 2: Find first node with < 2 children
Step 3: Insert new node as left or right child

Visualization

Tap to expand

Step-by-Step Walkthrough

BFS Traversal

Start from root, explore level by level

Find Gap

First node with missing child

Insert

Add new node, return parent value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct CBTInserter {
    struct TreeNode* root;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct CBTInserter* cBTInserterCreate(struct TreeNode* root) {
    struct CBTInserter* obj = (struct CBTInserter*)malloc(sizeof(struct CBTInserter));
    obj->root = root;
    return obj;
}

int cBTInserterInsert(struct CBTInserter* obj, int val) {
    if (!obj->root) {
        obj->root = createNode(val);
        return -1;
    }
    
    struct TreeNode* queue[10000];
    int front = 0, rear = 0;
    queue[rear++] = obj->root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (!node->left) {
            node->left = createNode(val);
            return node->val;
        } else if (!node->right) {
            node->right = createNode(val);
            return node->val;
        } else {
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        }
    }
    return -1;
}

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

int main() {
    printf("[null,1,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each insert requires complete BFS traversal of n nodes

✓ Linear Growth

Space Complexity

O(w)

BFS queue stores at most w nodes (width of tree level)

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Level Order Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler