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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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

1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val  # Node's value
7        self.left = left  # Node's left child
8        self.right = right  # Node's right child
9
10class CBTInserter:
11    def __init__(self, root: TreeNode):
12        # Initialize a list to store the nodes of the tree in level order
13        self.tree_nodes = []
14        # Start with a queue containing the root.
15        queue = deque([root])
16        # Perform breadth-first search to populate tree_nodes
17        while queue:
18            node = queue.popleft()
19            self.tree_nodes.append(node)
20            # Add left child if it exists
21            if node.left:
22                queue.append(node.left)
23            # Add right child if it exists
24            if node.right:
25                queue.append(node.right)
26
27    def insert(self, val: int) -> int:
28        # Calculate the parent index for the new node
29        parent_index = (len(self.tree_nodes) - 1) // 2
30        # Create a new node with the given value
31        new_node = TreeNode(val)
32        # Add the new node to the list of nodes
33        self.tree_nodes.append(new_node)
34        # Determine the parent node
35        parent_node = self.tree_nodes[parent_index]
36        # Decide where to add the new node in the parent
37        if not parent_node.left:
38            parent_node.left = new_node
39        else:
40            parent_node.right = new_node
41        # Return the value of the parent node
42        return parent_node.val
43
44    def get_root(self) -> TreeNode:
45        # Return the root node of the tree
46        return self.tree_nodes[0]
47
48# Usage Example:
49# To use this class, you would first instantiate it with a root TreeNode
50# cbt_inserter = CBTInserter(root)
51# To add a new node to the tree, you call the insert method
52# parent_val = cbt_inserter.insert(val)
53# To retrieve the current state of the tree root, call get_root
54# root = cbt_inserter.get_root()
55
1import java.util.ArrayDeque; // The ArrayDeque class is likely used for its deque capabilities.
2import java.util.ArrayList; // ArrayList is used to hold the TreeNode elements.
3import java.util.Deque; // Deque interface is used to create a double-ended queue.
4import java.util.List; // List interface is declared to generalize the usage of ArrayList.
5
6// Definition for a binary tree node.
7class TreeNode {
8    int val;
9    TreeNode left;
10    TreeNode right;
11
12    TreeNode() {}
13
14    TreeNode(int val) { this.val = val; }
15
16    TreeNode(int val, TreeNode left, TreeNode right) {
17        this.val = val;
18        this.left = left;
19        this.right = right;
20    }
21}
22
23class CBTInserter {
24    private List<TreeNode> treeNodes; // List to store the tree nodes in a level-order manner.
25
26    // Constructor to initialize the list with the given tree using level order traversal.
27    public CBTInserter(TreeNode root) {
28        treeNodes = new ArrayList<>();
29        Deque<TreeNode> queue = new ArrayDeque<>(); // Use Deque as a FIFO queue.
30        queue.offer(root);
31      
32        // Level order traversal to populate the list.
33        while (!queue.isEmpty()) {
34            TreeNode currentNode = queue.pollFirst();
35            treeNodes.add(currentNode);
36          
37            // Add left and right children to the queue if they exist.
38            if (currentNode.left != null) {
39                queue.offer(currentNode.left);
40            }
41            if (currentNode.right != null) {
42                queue.offer(currentNode.right);
43            }
44        }
45    }
46
47    // Inserts a node into the tree, adhering to the properties of a complete binary tree.
48    public int insert(int val) {
49        int parentId = (treeNodes.size() - 1) / 2; // Get the parent index.
50        TreeNode newNode = new TreeNode(val);
51        treeNodes.add(newNode); // The new node is added to the list.
52      
53        // Retrieve the parent node from the list.
54        TreeNode parentNode = treeNodes.get(parentId);
55        // If the left child does not exist, set it; otherwise, set the right child.
56        if (parentNode.left == null) {
57            parentNode.left = newNode;
58        } else {
59            parentNode.right = newNode;
60        }
61      
62        return parentNode.val; // Return the value of the parent where the node was inserted.
63    }
64
65    // This method returns the root of the tree.
66    public TreeNode getRoot() {
67        return treeNodes.get(0); // The first element in the list is the root.
68    }
69}
70
71/**
72 * Your CBTInserter object will be instantiated and called as such:
73 * CBTInserter obj = new CBTInserter(root);
74 * int param_1 = obj.insert(val);
75 * TreeNode param_2 = obj.getRoot();
76 */
77
1#include <vector>
2#include <queue>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode(int x = 0, TreeNode *left = nullptr, TreeNode *right = nullptr) 
10        : val(x), left(left), right(right) {}
11};
12
13// CBTInserter class definition that supports inserting into a complete binary tree.
14class CBTInserter {
15private:
16    std::vector<TreeNode*> treeNodes; // Vector to store tree nodes in breadth-first search order.
17
18public:
19    // Constructor to build the complete binary tree from root.
20    CBTInserter(TreeNode* root) {
21        std::queue<TreeNode*> queue;
22        queue.push(root);
23        // Use breadth-first search to construct the vector of tree nodes.
24        while (!queue.empty()) {
25            TreeNode* currNode = queue.front();
26            queue.pop();
27            treeNodes.push_back(currNode);
28            if (currNode->left) queue.push(currNode->left);
29            if (currNode->right) queue.push(currNode->right);
30        }
31    }
32
33    // Function to insert a new value as a node into the tree.
34    int insert(int val) {
35        // Find the parent's index for the new node.
36        int parentId = (treeNodes.size() - 1) / 2;
37        // Create a new node with the given value.
38        TreeNode* newNode = new TreeNode(val);
39        // Add the new node to the vector of tree nodes.
40        treeNodes.push_back(newNode);
41        // Retrieve the parent node from the vector.
42        TreeNode* parent = treeNodes[parentId];
43        // Determine if the new node is left or right child.
44        if (!parent->left)
45            parent->left = newNode;
46        else
47            parent->right = newNode;
48        // Return the value of the parent node.
49        return parent->val;
50    }
51
52    // Function to get the root of the tree.
53    TreeNode* getRoot() const {
54        // Return the first node in the vector, which is the root.
55        return treeNodes.empty() ? nullptr : treeNodes[0];
56    }
57};
58
59// Usage:
60// CBTInserter* obj = new CBTInserter(root);
61// int param_1 = obj->insert(val);
62// TreeNode* param_2 = obj->getRoot();
63
1// Global variable declaration for the root of the binary tree
2let root: TreeNode | null = null;
3
4// Queue to keep track of nodes which are not filled completely (either left or right child is missing)
5let queue: TreeNode[] = [];
6
7// Function to initialize the CBTInserter with the root of the binary tree
8function initialize(rootNode: TreeNode | null): void {
9    root = rootNode;
10    queue = [root];
11  
12    // Fill the queue by performing level-order traversal until we find a node without left or right child
13    while (true) {
14        let current = queue[0];
15        if (current.left === null) {
16            break;
17        }
18        queue.push(current.left);
19        if (current.right === null) {
20            break;
21        }
22        queue.push(current.right);
23        queue.shift(); // Remove the processed node from the queue
24    }
25}
26
27// Function to insert a new value into the tree and return the value of the parent node
28function insert(val: number): number {
29    // Ensure there is space for insertion
30    if (queue[0].left !== null && queue[0].right !== null) {
31        queue.shift(); // Parent is full, so remove it from the queue
32    }
33
34    // Create the new node
35    const newNode = new TreeNode(val);
36    // Add the new node to the queue
37    queue.push(newNode);
38
39    // Try to insert the new node to the left or right, depending on availability
40    if (queue[0].left === null) {
41        queue[0].left = newNode;
42        return queue[0].val;
43    }
44    if (queue[0].right === null) {
45        queue[0].right = newNode;
46        return queue[0].val;
47    }
48
49    // In case both left and right nodes are present, return 0 (though this case should be covered above)
50    return 0;
51}
52
53// Function to return the root of the binary tree
54function getRoot(): TreeNode | null {
55    return root;
56}
57
58// Definition for a binary tree node.
59class TreeNode {
60    val: number;
61    left: TreeNode | null;
62    right: TreeNode | null;
63  
64    // TreeNode constructor
65    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
66        this.val = val === undefined ? 0 : val;
67        this.left = left === undefined ? null : left;
68        this.right = right === undefined ? null : right;
69    }
70}
71
72// Example usage
73// initialize(root); // root should be predefined TreeNode or null
74// let parentVal1 = insert(1); // Returns the value of the parent of the node that was inserted
75// let parentVal2 = insert(2); // Same here
76// let currentRoot = getRoot(); // Retrieves the current root of the tree
77

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.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄