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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Complete Binary Tree Inserter

Difficulty: Medium

Problem Description

Design an algorithm to insert a new node to a complete binary tree keeping it complete after the insertion. Implement the CBTInserter class with the following methods:

  • 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.

Key Insights

  • A complete binary tree is filled from top to bottom and left to right.
  • The insertion can be done effectively by maintaining a queue to track the nodes at the current level of the tree.
  • The new node should always be added as a child to the first available parent node in the queue.

Space and Time Complexity

Time Complexity: O(1) for insert operation, O(n) for get_root operation.
Space Complexity: O(n) for storing the queue that tracks the nodes in the tree.

Solution

To solve this problem, we use a queue to keep track of the nodes on the current level of the complete binary tree. Upon initialization, we traverse the tree level-by-level using a breadth-first search (BFS) approach to populate this queue. When a new value is inserted, we always add the new node as a child of the first node in the queue that has an available position. After insertion, if the parent node is fully occupied, it is removed from the queue, ensuring that the queue always contains nodes that can accept new children.

Code Solutions

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):
        self.root = root
        self.queue = deque([root])
        while self.queue:
            node = self.queue[0]  # Peek at the front of the queue
            if node.left:
                self.queue.append(node.left)
            if node.right:
                self.queue.append(node.right)
                self.queue.popleft()  # Remove the node if it has two children
            else:
                break  # Found a node without a right child

    def insert(self, v: int) -> int:
        new_node = TreeNode(v)
        parent = self.queue[0]  # The parent for the new node
        if not parent.left:
            parent.left = new_node
        else:
            parent.right = new_node
            self.queue.popleft()  # Remove parent if it now has two children
        self.queue.append(new_node)  # Add new node to the queue
        return parent.val

    def get_root(self) -> TreeNode:
        return self.root
← Back to All Questions