LeetCode 919 - Complete Binary Tree Inserter

This problem asks us to design a data structure that allows insertion into a complete binary tree while maintaining its completeness. A complete binary tree is one where all levels are fully filled, except possibly the last, which is filled from left to right.

leetcodemediumtreebreadth-first-searchdesignbinary-tree

LeetCode Problem 919

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Design, Binary Tree

Solution

Problem Understanding

This problem asks us to design a data structure that allows insertion into a complete binary tree while maintaining its completeness. A complete binary tree is one where all levels are fully filled, except possibly the last, which is filled from left to right. The key requirement is that after each insertion, the tree must remain complete.

We are given the root of an existing complete binary tree, and we must implement three operations. First, the constructor CBTInserter(TreeNode root) initializes our data structure with the tree. Second, insert(int val) adds a new node while keeping the tree complete and returns the value of its parent node. Third, get_root() simply returns the root node of the tree.

The constraints tell us that the tree can have up to 1000 nodes initially, and we may call insert up to 10,000 times. This indicates that a solution that performs a full tree traversal on every insertion would be too slow, because repeated traversals could yield O(n) per insert, which accumulates to O(n * 10^4). Additionally, all node values are small non-negative integers, which does not affect the structure, but simplifies storage.

Edge cases include a tree with a single node (insertions must create children of the root first), a nearly complete tree with the last level partially filled (insertions must correctly find the leftmost available position), and multiple sequential insertions that fill several levels.

Approaches

Brute Force Approach

A naive solution is to perform a level-order traversal (BFS) on the tree every time we want to insert a node. We would enqueue all nodes in a queue and traverse from left to right. The first node we encounter without a left or right child becomes the parent for the new node. This guarantees correctness because BFS ensures we always process nodes level by level, filling the leftmost available positions first.

While correct, this approach is inefficient. Each insertion requires traversing potentially the entire tree, which is O(n) per insert. If there are many insertions, the total time can become O(n * k), where k is the number of insertions, leading to unacceptable performance.

Optimal Approach

The key insight is to maintain a queue of candidate parent nodes that currently have fewer than two children. During initialization, we perform a single BFS to populate this queue. Then, each insertion simply takes the first node in the queue as the parent, adds the new node as its left or right child, and if the parent now has two children, we remove it from the queue. The new node is always appended to the end of the queue because it may become a parent in future insertions.

This approach is efficient because each insertion is O(1) amortized. The initial BFS traversal is O(n), but this only happens once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per insert O(n) Traverse entire tree to find insertion point each time
Optimal O(1) per insert after O(n) init O(n) Maintain queue of nodes with less than 2 children to quickly insert

Algorithm Walkthrough

  1. Initialization (Constructor): Start with the root node. Perform a level-order traversal (BFS) of the tree. For each node, if it has fewer than two children, add it to the candidate queue. This queue represents nodes eligible to receive a new child.
  2. Insert Operation: Take the node at the front of the candidate queue as the parent. If it has no left child, add the new node as its left child. Otherwise, add it as the right child. If the parent now has two children, remove it from the queue. Append the newly inserted node to the back of the queue because it may receive children in the future. Return the value of the parent node.
  3. Get Root Operation: Simply return the root node stored during initialization.

Why it works: The invariant is that the candidate queue always contains nodes with fewer than two children, ordered by level-order traversal. This ensures that every insertion fills the leftmost available position in the tree, preserving completeness.

Python Solution

from collections import deque
from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class CBTInserter:

    def __init__(self, root: Optional[TreeNode]):
        self.root = root
        self.candidates = deque()
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if not node.left or not node.right:
                self.candidates.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def insert(self, val: int) -> int:
        parent = self.candidates[0]
        new_node = TreeNode(val)
        if not parent.left:
            parent.left = new_node
        else:
            parent.right = new_node
            self.candidates.popleft()
        self.candidates.append(new_node)
        return parent.val

    def get_root(self) -> Optional[TreeNode]:
        return self.root

Explanation: The constructor populates a deque candidates with nodes that have fewer than two children. insert always uses the first candidate and adds the new node accordingly. After insertion, the deque is updated to maintain the invariant. get_root simply returns the stored root.

Go Solution

package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

type CBTInserter struct {
    root *TreeNode
    candidates []*TreeNode
}

func Constructor(root *TreeNode) CBTInserter {
    c := CBTInserter{root: root}
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
        if node.Left == nil || node.Right == nil {
            c.candidates = append(c.candidates, node)
        }
    }
    return c
}

func (this *CBTInserter) Insert(val int) int {
    parent := this.candidates[0]
    newNode := &TreeNode{Val: val}
    if parent.Left == nil {
        parent.Left = newNode
    } else {
        parent.Right = newNode
        this.candidates = this.candidates[1:]
    }
    this.candidates = append(this.candidates, newNode)
    return parent.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
    return this.root
}

Explanation: Go uses slices instead of deque, so the first element is accessed by index 0. Removal of the first element is done with slicing (this.candidates = this.candidates[1:]). Otherwise, the logic mirrors the Python version exactly.

Worked Examples

Example 1

Input operations:

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

Step 1: Constructor

  • Queue = [1, 2]
  • Candidates deque after BFS = [1, 2] because node 1 has only left child, node 2 has 0 children

Step 2: insert(3)

  • Parent = 1
  • Node 3 becomes 1.right
  • Node 1 now has two children → remove 1 from candidates
  • Append 3 to candidates
  • Return 1

Candidates = [2, 3]

Step 3: insert(4)

  • Parent = 2
  • Node 4 becomes 2.left
  • Node 2 has only left → remains in candidates
  • Append 4 to candidates
  • Return 2

Candidates = [2, 3, 4]

Step 4: get_root()

  • Returns root node with tree structure:
        1
       / \
      2   3
     /
    4

Complexity Analysis

Measure Complexity Explanation
Time O(n) init, O(1) per insert Initialization does BFS over n nodes; subsequent inserts touch only a candidate node
Space O(n) Queue of candidate nodes can grow up to O(n) in worst case

The space is dominated by storing candidates in a deque or slice. Each insertion only updates pointers, so it is very efficient.

Test Cases

# Basic example
root = TreeNode(1, TreeNode(2))
obj = CBTInserter(root)
assert obj.insert(3) == 1  # insert to root
assert obj.insert(4) == 2  # insert to node 2
assert obj.get_root().val == 1  # root value

# Single node tree
root = TreeNode(1)
obj = CBTInserter(root)
assert obj.insert(2) == 1  # left child
assert obj.insert(3) == 1  # right child

# Full two-level tree
root = TreeNode(1, TreeNode(2), TreeNode(3))
obj = CBTInserter(root)
assert obj.insert(4) == 2  # left