Complete Binary Tree Inserter

Medium

Asked by:

44 views

Topics:

Trees

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the tree? Are negative values allowed?
Is the initial tree guaranteed to be a complete binary tree, or could it be any binary tree?
What value should I return from the `insert` function?
If the initial tree is empty (root is null), how should the `get_root` function behave after multiple insertions?
How should I handle integer overflow in the node values or in any calculations during insertion?

Brute Force Solution

Approach

The problem involves adding new values to a binary tree, making sure it stays 'complete'. A brute force solution involves checking all potential locations for the new value, level by level, until we find an available spot.

Here's how the algorithm would work step-by-step:

When we need to add a new value, we'll start by examining the very first level of the tree.
We check if the first level is full. If not, we insert the value there.
If the first level is full, we move to the next level and repeat the checking process.
We continue this level-by-level exploration until we find the first available empty spot in the tree where we can insert the new value.
Once we've inserted the value, we stop the search, because we've found the correct location to maintain the 'complete' property of the tree.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class CBTInserter:

    def __init__(self, root):
        self.root = root

    def insert(self, value):
        queue = [self.root]
        
        while queue:
            level_size = len(queue)

            # Traverse the current level
            for _ in range(level_size):
                node = queue.pop(0)

                # If the left child is empty, insert the new node there
                if not node.left:
                    node.left = TreeNode(value)
                    return node.value

                # If the right child is empty, insert the new node there
                if not node.right:
                    node.right = TreeNode(value)
                    return node.value

                # Add the children to the queue for the next level
                queue.append(node.left)
                queue.append(node.right)

    def get_root(self):
        return self.root

Big(O) Analysis

Time Complexity

O(n) – The provided brute force approach involves traversing the tree level by level until an empty spot is found. In the worst-case scenario, we might have to traverse almost all nodes in the tree to find the correct insertion point. Since a complete binary tree with n nodes has a height of approximately log n, and each level can have at most half the number of nodes as the total tree size, we can say that in the worst case we visit nearly all nodes. Thus, the time complexity is proportional to the number of nodes, n, resulting in O(n).

Space Complexity

O(W) – The level-by-level exploration, as described, suggests a breadth-first search (BFS) approach, even though not explicitly mentioned. This implies the use of a queue to hold nodes at each level during the search. In the worst-case scenario, the queue might contain all nodes at the widest level of the complete binary tree. The width of the widest level is proportional to W, where W is the maximum width of the tree. Therefore, the auxiliary space is primarily determined by the size of the queue, which can grow up to the maximum width of the tree, W. This results in a space complexity of O(W).

Optimal Solution

Approach

The goal is to add new values to a binary tree, filling it level by level from left to right. The key idea is to keep track of which nodes might need children added to them, so we don't have to search the whole tree every time we add a new value.

Here's how the algorithm would work step-by-step:

When our object is first created, find all nodes that currently have either zero or one child. These are the potential spots to add new nodes.
Keep these potential spots in an ordered list (like a line).
When we add a new value, take the first node from the list of potential spots.
Add the new value as either the left or right child of this node, depending on which one is missing.
If that node now has two children, remove it from the list of potential spots because it's now full.
Add the new node we just created to the back of the list of potential spots, because it will eventually need children itself.
Return the value of the parent node where we added the new child.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class CBTInserter:

    def __init__(self, root):
        self.root_node = root
        self.potential_parents = []

        queue = [root]
        while queue:
            node = queue.pop(0)
            if not node.left or not node.right:
                self.potential_parents.append(node)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def insert(self, value):
        # Select the first potential parent.
        parent_node = self.potential_parents[0]

        new_node = TreeNode(value)

        if not parent_node.left:
            parent_node.left = new_node
        else:
            parent_node.right = new_node
            # Parent is full, so remove from potential parents.
            self.potential_parents.pop(0)

        # New node could need children later.
        self.potential_parents.append(new_node)

        return parent_node.value

    def get_root(self):
        return self.root_node

Big(O) Analysis

Time Complexity

O(n) – The constructor finds all nodes with 0 or 1 children in the initial tree of n nodes. This involves traversing the tree, which takes O(n) time. The insert function adds a new node by retrieving the first element in a list, updating it, and appending the new node to the end of the list. These operations within the insert function take O(1) time each. Therefore, the time complexity is dominated by the initial tree traversal in the constructor, resulting in O(n) overall.

Space Complexity

O(N) – The auxiliary space is dominated by the queue (or list) used to store the nodes that potentially need children. In the worst-case scenario, the complete binary tree is skewed such that the last level has approximately N/2 nodes, and many of the nodes in the previous levels will also be stored in the list before they have two children. Thus, the list can hold a number of nodes proportional to N, where N is the total number of nodes in the tree. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null root node in constructor	Handle null root by initializing an empty tree and queue, or throwing an exception if null root is invalid.
Inserting into a perfectly complete tree.	The solution should correctly add nodes to the next level upon filling the last node in the deepest level.
Very large number of insert calls causing integer overflow if tracked improperly	Use a data type with sufficient range (e.g., long) for tracking insertion count or use the tree structure itself to guide insertion.
Tree with a single root node initially.	Insertion should correctly add left and right children to the root node and update the queue.
Nodes with extremely large values (close to max int).	Ensure the `insert` method can handle large integer values without overflow during comparison or arithmetic operations, but this should be naturally handled by Java unless doing specific manual operations.
Skewed tree (e.g., all nodes only have left children).	The algorithm should still correctly add nodes to the appropriate position based on the complete tree property, even with a skewed tree.
Inserting a node with a value that already exists in the tree.	The problem doesn't explicitly state uniqueness, so handle duplicate values by simply inserting the new node as per the complete tree insertion rules.
Extremely deep tree with many nodes, potentially causing memory issues if the queue grows too large	The queue should only contain nodes that are missing children, so memory usage should be proportional to the number of incomplete nodes, not the total number of nodes, which should be acceptable.

Null root node in constructor

How to Handle:

Handle null root by initializing an empty tree and queue, or throwing an exception if null root is invalid.

Inserting into a perfectly complete tree.

How to Handle:

The solution should correctly add nodes to the next level upon filling the last node in the deepest level.

Very large number of insert calls causing integer overflow if tracked improperly

How to Handle:

Use a data type with sufficient range (e.g., long) for tracking insertion count or use the tree structure itself to guide insertion.

Tree with a single root node initially.

How to Handle:

Insertion should correctly add left and right children to the root node and update the queue.

Nodes with extremely large values (close to max int).

How to Handle:

Ensure the `insert` method can handle large integer values without overflow during comparison or arithmetic operations, but this should be naturally handled by Java unless doing specific manual operations.

Skewed tree (e.g., all nodes only have left children).

How to Handle:

The algorithm should still correctly add nodes to the appropriate position based on the complete tree property, even with a skewed tree.

Inserting a node with a value that already exists in the tree.

How to Handle:

The problem doesn't explicitly state uniqueness, so handle duplicate values by simply inserting the new node as per the complete tree insertion rules.

Extremely deep tree with many nodes, potentially causing memory issues if the queue grows too large

How to Handle:

The queue should only contain nodes that are missing children, so memory usage should be proportional to the number of incomplete nodes, not the total number of nodes, which should be acceptable.