919. Complete Binary Tree Inserter

Problem Description

The problem defines a complete binary tree where every level except the last is completely filled, and all nodes are shifted as left as possible. We're tasked to create an algorithm that can insert a new node into this complete binary tree such that the tree remains complete after the insertion.

To maintain the completeness of the tree, we must insert the new node at the leftmost position available on the last level of the tree. If the last level is full, the new node should be placed as the leftmost node on a new level.

The problem statement also requires us to implement a class CBTInserter that has the following functionalities:

• Initializing the data structure with an existing complete binary tree's root.
• Inserting a new node with a specified value into the tree in a way that maintains the tree's complete nature.
• Retrieving the root node of the tree.

Intuition

To intuitively approach this problem, we consider a level-order traversal, which visits each node from top to bottom and from left to right. This traversal naturally fits with the property of a complete binary tree as it fills up from left to right, level by level.

The intuition behind the solution is to keep track of all the nodes in the tree using a list self.tree to facilitate the insertion process. By doing this, we can easily find the parent for the new node since the list maintains the order of the nodes as they would be encountered in a level-order traversal.

• As the first step, we perform a level-order traversal of the tree using a queue to initially populate self.tree.
• For insertion, the parent node of the new node to be inserted is found at index ((len(self.tree) - 1) // 2). This works because in a zero-indexed list that represents a complete binary tree, the children of the node at index i are found at indices 2*i + 1 (for the left child) and 2*i + 2 (for the right child).
• We then create a new TreeNode with the value val and add it to self.tree.
• The new node is linked to the parent node by checking whether the parent’s left child is None. If it is, the new node becomes the left child, else it becomes the right child.
• The value of the parent of the newly inserted node is returned as per the problem requirements.
• The get_root method is straightforward as it returns the root node of the tree, which is the first element in self.tree.

With this approach, every insert operation ensures that the tree remains a complete binary tree and is done in O(1) time complexity caused by the parent lookup and insertion at the end of self.tree.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Solution Approach

The implementation of the solution uses a Breadth-First Search (BFS) algorithm for level-order traversal and a deque data structure from Python's collections for efficient removal of elements from the front. The BFS is ideal for level-order traversal of a complete binary tree, which helps to initialize the data structure with the existing complete binary tree.

Here's a breakdown of the algorithm and data structures used in the CBTInserter class implementation:

• Initialization (The Constructor): We use a queue (deque) to store nodes in a level-order traversal starting with the root. While the queue is not empty:

  • We take out the front node from the queue.
  • Append the node to the self.[tree](/problems/tree_intro) list, which will store the nodes in the same order as level-order traversal.
  • If the node has a left child, it's also added to the queue, followed by the right child (if any).

  This process "flattens" the binary tree into the self.tree list while preserving the level order, thus giving us direct access to parents for each potential new node insertion.

1def __init__(self, root: TreeNode):
2    self.[tree](/problems/tree_intro) = []
3    q = deque([root])
4    while q:
5        node = q.popleft()
6        self.tree.append(node)
7        if node.left:
8            q.append(node.left)
9        if node.right:
10            q.append(node.right)

• Insert Method: When we want to insert a new node, val, we need to determine the parent node:

  • The parent's index for the new node can be calculated easily since the self.[tree](/problems/tree_intro) list maintains a level-order sequence. The formula to find the parent index is ((len(self.tree) - 1) // 2).
  • We then instantiate a new TreeNode with the given val.
  • We decide where to add the new node as a child (left or right) of the found parent based on the presence of a left child.
  • Finally, we append the new node to the self.tree list to maintain the level-order structure and return the value of the parent node as required.

1def insert(self, val: int) -> int:
2    pid = (len(self.[tree](/problems/tree_intro)) - 1) >> 1
3    node = TreeNode(val)
4    self.tree.append(node)
5    p = self.tree[pid]
6    if p.left is None:
7        p.left = node
8    else:
9        p.right = node
10    return p.val

• Get Root Method: This method is quite straightforward as it simply returns the root of the tree, which is always the first element of self.tree list since this list represents the level-order traversal of the nodes.

1def get_root(self) -> TreeNode:
2    return self.[tree](/problems/tree_intro)[0]

By keeping track of the nodes in level-order within an array, this approach streamlines the process of finding a parent node for insertion, and efficiently implements a complete binary tree inserter, satisfying the problem's requirements.

Example Walkthrough

Let's take a simple complete binary tree to illustrate the solution approach and see how the CBTInserter class would handle the insertion of a new node.

Consider a complete binary tree with the following structure:

1       1
2      / \
3     2   3
4    / 
5   4   

When we initialize our CBTInserter with this tree, during creation, the constructor performs a level-order traversal and adds these nodes to self.tree. After the constructor has run, self.tree will contain the nodes in the order they were visited (level order): [1, 2, 3, 4].

Now let's insert a new node with value 5 into the tree.

1. We calculate the parent index using the formula pid = (len(self.tree) - 1) // 2. Since len(self.tree) is 4, the parent index pid will be (4 - 1) // 2, which equals 1. This means that the parent node is at index 1 in self.tree, which corresponds to the node with value 2.

2. We create a new TreeNode with the value 5 and add it to self.tree.

3. We then check if the node with value 2 (self.tree[1]) has a left child. It does, so we add the new node as a right child.

The tree now looks like this:

1       1
2      / \
3     2   3
4    / \
5   4   5   

Finally, self.tree is now [1, 2, 3, 4, 5], ensuring that the level-order structure is preserved.

The insert method would then return the value of the parent node, which is 2.

Next, suppose we insert another node with value 6:

1. This time, len(self.tree) is 5, so the parent index pid will be (5 - 1) // 2, which equals 2. The parent node is thus the one with value 3 (self.tree[2]).

2. We create a new TreeNode with the value 6 and append it to self.tree.

3. Since the node with value 3 (self.tree[2]) has no children yet, we add the new node as its left child.

After this insertion, the tree becomes:

1       1
2      / \
3     2   3
4    / \  /
5   4   5 6

And self.tree updates to [1, 2, 3, 4, 5, 6].

The insert method returns the value 3, the value of the parent where the new node is inserted.

Using this process, we can continue to insert nodes while maintaining the properties of a complete binary tree. The get_root() method remains simple: it just returns the first element in self.tree, which is always the root node. In this scenario, get_root() would return the node with value 1.

Solution Implementation

Time and Space Complexity

__init__ constructor

The __init__ function of class CBTInserter involves a breadth-first search (BFS) through the tree, which visits all nodes exactly once. If the tree has n nodes, the time complexity of this operation is O(n). There is no extra space utilized that scales with the input, since the deque q is being used to only keep track of the nodes at the current level, but we won’t need more space than O(n) because the list self.tree will store all nodes anyway. Hence, the space complexity of the constructor is O(n).

insert function

The insert function computes the parent index pid with a constant-time operation and then appends the new node to self.tree. The complexity of appending to the end of a list in Python is O(1) assuming that the list does not need to resize its internal array. Accessing and modifying the parent node's child is also done in constant time, thus the time complexity of insert is O(1) on average. No additional space is allocated during the insert operation, so the space complexity remains O(1).

get_root function

The get_root method returns the root of the tree, which is the first element of self.tree. Accessing the first element of a list is a constant-time operation, so the time complexity is O(1), and there is no additional space used, so the space complexity is also O(1).

Overall, the CBTInserter class performs its operations efficiently, with the __init__ method taking linear time relative to the number of nodes in the initial tree and both insert and get_root methods operating in constant time.

Learn more about how to find time and space complexity quickly using problem constraints.