We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Complete Binary Tree Inserter

Number: 955

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, PhonePe, TikTok, Google

Problem Description

Design a data structure that supports insertion into a complete binary tree while maintaining its completeness. The data structure is initialized with the root of a complete binary tree, and then supports insertions that attach a new node with a given value in the appropriate position and returns the value of its parent. It also supports returning the root of the tree.

Key Insights

  • Use a Breadth-First Search (BFS) approach to initially traverse the tree and identify nodes that do not have two children.
  • Maintain a queue (or list) of candidate nodes that are incomplete (i.e., have less than two children). This enables constant time retrieval of the next insertion point.
  • On each insertion, update the candidate list: if a node acquires its second child, remove it from the candidate list, and add the new node as a candidate.

Space and Time Complexity

Time Complexity: O(1) on average per insert, as we maintain a queue that gives immediate access to the next insertion point. Space Complexity: O(n), where n is the number of nodes in the tree, since we store pointers to nodes in the queue.

Solution

The solution begins by performing a level-order traversal (BFS) to collect all nodes that do not have two children. This queue forms the basis for efficient insertion. For each new insertion:

  • Look at the first node in the queue (the current candidate parent).
  • If the candidate does not have a left child, insert the new node as the left child.
  • Otherwise, insert it as the right child and remove the candidate from the queue because it now has both children.
  • Add the newly inserted node to the queue since it can potentially have children in future insertions. This approach ensures that the tree remains complete after every insertion.

Code Solutions

# 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

from collections import deque
class CBTInserter:
    def __init__(self, root: TreeNode):
        # Initialize the deque with nodes that are candidates for insertion.
        self.root = root
        self.deque = deque()
        queue = deque([root])
        while queue:
            node = queue.popleft()
            # If the node is missing a child, it is a candidate for insertion.
            if not node.left or not node.right:
                self.deque.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def insert(self, v: int) -> int:
        # The front of the deque is the candidate parent.
        parent = self.deque[0]
        new_node = TreeNode(v)
        if not parent.left:
            # Insert as left child.
            parent.left = new_node
        else:
            # Insert as right child.
            parent.right = new_node
            # Once a node has both children, remove it.
            self.deque.popleft()
        # Add the new node as it might be a candidate for future insertions.
        self.deque.append(new_node)
        return parent.val

    def get_root(self) -> TreeNode:
        # Return the root of the tree.
        return self.root
← Back to All Questions