LeetCode 919: Complete Binary Tree Inserter Solution

Master LeetCode problem 919 (Complete Binary Tree Inserter), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

919. Complete Binary Tree Inserter

Medium

Tree Breadth-First Search Design Binary Tree

Problem Explanation

Explanation

To implement the CBTInserter class, we can use a queue to perform level order traversal and insert the new node in the correct position to keep the tree complete. We will maintain a queue of nodes that are not full (i.e., nodes with less than 2 children). When inserting a new node, we will find the first node from the front of the queue, add the new node as its child, and if that node becomes full (i.e., has 2 children), we remove it from the queue.

Algorithm:

Initialize the queue with the root node.
When inserting a node, take the first node from the front of the queue.
If the first node doesn't have a left child, add the new node as its left child.
Otherwise, add the new node as its right child and remove the first node from the queue.
Return the value of the parent node of the inserted node.
Repeat the process until the tree is complete.

Time Complexity:

insert operation: O(1) (amortized time complexity)
get_root operation: O(1)

Space Complexity:

O(n) where n is the number of nodes in the binary tree.

Solution Code

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class CBTInserter {
    private TreeNode root;
    private Queue<TreeNode> queue;

    public CBTInserter(TreeNode root) {
        this.root = root;
        this.queue = new LinkedList<>();
        Queue<TreeNode> temp = new LinkedList<>();
        temp.offer(root);
        while (!temp.isEmpty()) {
            TreeNode node = temp.poll();
            if (node.left == null || node.right == null) {
                queue.offer(node);
            }
            if (node.left != null) temp.offer(node.left);
            if (node.right != null) temp.offer(node.right);
        }
    }

    public int insert(int v) {
        TreeNode parent = queue.peek();
        TreeNode node = new TreeNode(v);
        queue.offer(node);
        if (parent.left == null) {
            parent.left = node;
        } else {
            parent.right = node;
            queue.poll();
        }
        return parent.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 919 (Complete Binary Tree Inserter)?

This page provides optimized solutions for LeetCode problem 919 (Complete Binary Tree Inserter) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 919 (Complete Binary Tree Inserter)?

The time complexity for LeetCode 919 (Complete Binary Tree Inserter) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 919 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 919 in Java, C++, or Python.

Back to LeetCode Solutions