Complete Binary Tree Inserter - Solution & Explanation

Q: Is Complete Binary Tree Inserter easy or hard?

Complete Binary Tree Inserter is rated Medium difficulty on LeetCode with an acceptance rate around 65%. The challenge is recognizing that you should maintain a queue of incomplete nodes instead of scanning the tree every time you insert.

Q: Complete Binary Tree Inserter Python/Java solution

Python solutions typically use collections.deque to maintain the candidate parent queue. Java implementations commonly use a LinkedList or ArrayDeque for the same BFS queue structure. Both languages implement the same logic: preprocess the tree, then perform O(1) insert operations.

Q: How to solve Complete Binary Tree Inserter in O(n)?

Run a level-order traversal to find the first node missing a child and insert there. If you repeat this traversal for every insert, the operation costs O(n) time. A more efficient design precomputes candidate parents using BFS so that later insertions become O(1).

Q: What is the best approach for Complete Binary Tree Inserter?

The optimal approach maintains a queue of nodes that are missing at least one child. During initialization, perform a BFS to populate this queue. Each insertion attaches the new node to the front node in the queue and updates the queue accordingly. This design gives O(1) insertion time after an O(n) preprocessing step.

Q: Is Complete Binary Tree Inserter asked at Google/Amazon/Meta?

Tree design and BFS-based insertion problems appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of complete binary tree properties, queue-based traversal, and data structure design patterns.

Q: What data structure is used in Complete Binary Tree Inserter?

The core data structure is a queue used for breadth-first traversal. The queue stores nodes that do not yet have two children, allowing constant-time access to the next valid parent during insertion. The tree itself is represented using standard binary tree nodes.

Q: What is the time complexity of Complete Binary Tree Inserter?

Using the optimized BFS queue design, initialization takes O(n) time to scan the existing tree. Each insert operation runs in O(1) time because the next valid parent is already tracked in a queue. Space complexity is O(n) for storing candidate parent nodes.

MediumTree Breadth-First Search Design Binary Tree18 min readAsked at: Amazon, Meta, Google

Practice this problem

Problem Statement

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 10⁴ calls will be made to insert and get_root.

Approach Overview

Problem Overview: Design a class that inserts nodes into a complete binary tree while preserving the complete-tree property. Each insertion must place the new node in the leftmost available position of the last level and return the parent node's value.

Approach 1: Breadth-First Search using a Queue (Initialization O(n), Insert O(1) time, O(n) space)

The key observation: in a complete binary tree, insertion always happens at the first node that is missing a child. During initialization, run a breadth-first search and push every node with fewer than two children into a queue. The front of the queue always represents the next valid parent for insertion. When inserting, attach the new node as the left child if missing, otherwise as the right child and remove the parent from the queue because it is now full. Add the new node to the queue since it may accept future children. Initialization costs O(n) time, but each insert() runs in O(1) time with O(n) space for the queue.

Approach 2: Level Order Traversal for Insertion (O(n) time per insert, O(n) space)

This method performs a fresh level-order traversal every time you insert a node. Starting from the root, use a queue to scan nodes level by level until you find the first node that does not have two children. Insert the new node as the left child if it is empty; otherwise attach it to the right. The traversal guarantees the complete-tree property because nodes are explored strictly from left to right across each level. The downside is repeated work: each insertion may scan the entire binary tree, leading to O(n) time per operation and O(n) auxiliary queue space.

Recommended for interviews: The queue-based BFS design is the expected solution. It preprocesses the tree once and keeps a list of candidate parents, turning insertion into a constant-time operation. Interviewers like this approach because it demonstrates understanding of tree structure invariants and efficient state maintenance. The level-order traversal method is easier to reason about initially and shows understanding of the complete-tree property, but the optimized queue design proves stronger algorithmic thinking.

Approach 1: Approach 1: Breadth-First Search using a Queue

The idea is to use a queue to track the nodes at the current level and help find where to insert a new node to maintain the complete binary tree property.

When inserting, always maintain a queue that holds nodes which can potentially have children added to them. Initially, populate the queue with nodes from the complete tree using level-order traversal where a node is added only if it can further accommodate more children.

For each insertion, take the node from the front of the queue and insert the new child. If a node has both children filled after insertion, remove it from the queue. New nodes always get added to the end of the queue to maintain the complete binary tree property.

We initialize the class by performing a level-order traversal of the tree to add each node to a queue if it can have children nodes added.

During insertion, we check the first node in our queue for having a room for a new child (left or right). We insert the new node, if both children nodes are filled, then we remove the parent from the queue as it's full and add the newly inserted node to maintain order.

Time complexity for initializing the class constructor is O(n) and for insert operation is O(1).

Code

Python C

Python

Complexity

Both the insertion and retrieving the root operations run with O(1) time complexity. The space complexity is O(n) for storing nodes in the deque.

Try this approach in the editor →

Approach 2: Approach 2: Level Order Traversal for Insertion

This approach still employs a level order traversal starting from the root for every insertion to find the first available spot, thus maintaining the complete binary tree properties.

With each insertion, traverse the tree using a queue to ensure for each node, you check if it is either missing a left or right child. Stop and insert the new node at the first possible position found.

Even though this method is less efficient during each insert because of repeated traversal, it effectively maintains tree completeness by directly probing the current state of the tree.

In this Java solution, for every insert call, we perform a level order traversal from the root node to find where the new value should go. A standard queue supports the traversal to ensure the completeness property of the binary tree.

The get_root operation directly returns the stored root. This approach can be less optimal than using a persistent queue but systematically searches for the next possible insertion point.

Code

Java JavaScript

Java

JavaScript

Complexity

For the `insert` method, the time complexity per insertion operation can reach O(n) in the worst case if re-traversing the tree is required. The `get_root` call is O(1).

Space complexity is O(n) for managing the additional queue during the insertion process.

Try this approach in the editor →

Approach 3: BFS

We can use an array tree to store all nodes of the complete binary tree. During initialization, we use a queue q to perform level-order traversal of the given tree and store all nodes into the array tree.

When inserting a node, we can find the parent node p of the new node through the array tree. Then we create a new node node, insert it into the array tree, and make node as the left child or right child of p. Finally, we return the value of p.

When getting the root node, we directly return the first element of the array tree.

In terms of time complexity, it takes O(n) time for initialization, and the time complexity for inserting a node and getting the root node are both O(1). The space complexity is O(n), where n is the number of nodes in the tree.

Code

Python Java C++Go TypeScript JavaScript

Python

Java

C++

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Breadth-First Search using a Queue	Both the insertion and retrieving the root operations run with O(1) time complexity. The space complexity is O(n) for storing nodes in the deque.
Approach 2: Level Order Traversal for Insertion	For the `insert` method, the time complexity per insertion operation can reach O(n) in the worst case if re-traversing the tree is required. The `get_root` call is O(1). Space complexity is O(n) for managing the additional queue during the insertion process.
BFS	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Breadth-First Search Queue (Candidate Parents)	Init: O(n), Insert: O(1)	O(n)	Best choice for repeated insert operations and interview solutions
Level Order Traversal Per Insert	O(n) per insert	O(n)	Simple approach when insert operations are rare or for conceptual understanding

Video Solution

Complete Binary Tree Inserter • Pepcoding • 3,111 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Complete Binary Tree Inserter easy or hard?

Complete Binary Tree Inserter is rated Medium difficulty on LeetCode with an acceptance rate around 65%. The challenge is recognizing that you should maintain a queue of incomplete nodes instead of scanning the tree every time you insert.

Complete Binary Tree Inserter Python/Java solution

Python solutions typically use collections.deque to maintain the candidate parent queue. Java implementations commonly use a LinkedList or ArrayDeque for the same BFS queue structure. Both languages implement the same logic: preprocess the tree, then perform O(1) insert operations.

How to solve Complete Binary Tree Inserter in O(n)?

Run a level-order traversal to find the first node missing a child and insert there. If you repeat this traversal for every insert, the operation costs O(n) time. A more efficient design precomputes candidate parents using BFS so that later insertions become O(1).

What is the best approach for Complete Binary Tree Inserter?

The optimal approach maintains a queue of nodes that are missing at least one child. During initialization, perform a BFS to populate this queue. Each insertion attaches the new node to the front node in the queue and updates the queue accordingly. This design gives O(1) insertion time after an O(n) preprocessing step.

Is Complete Binary Tree Inserter asked at Google/Amazon/Meta?

Tree design and BFS-based insertion problems appear frequently in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of complete binary tree properties, queue-based traversal, and data structure design patterns.

What data structure is used in Complete Binary Tree Inserter?

The core data structure is a queue used for breadth-first traversal. The queue stores nodes that do not yet have two children, allowing constant-time access to the next valid parent during insertion. The tree itself is represented using standard binary tree nodes.

What is the time complexity of Complete Binary Tree Inserter?

Using the optimized BFS queue design, initialization takes O(n) time to scan the existing tree. Each insert operation runs in O(1) time because the next valid parent is already tracked in a queue. Space complexity is O(n) for storing candidate parent nodes.

Ready to solve this problem?

Practice Complete Binary Tree Inserter with our built-in code editor and test cases.

Practice on FleetCode

Binary Tree Inorder Traversal

Unique Binary Search Trees II

Problem Info

DifficultyMedium

Acceptance65.0%

Approaches3

Reading time18 min

Asked at

Amazon Meta Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Breadth-First Search using a Queue

Code

Complexity

Approach 2: Approach 2: Level Order Traversal for Insertion

Code

Complexity

Approach 3: BFS

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents