Introduction

In this blog post, we will explore how to solve the LeetCode problem "919" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 104 calls will be made to insert and get_root.

Explanation

• Initialization: During initialization, perform a level-order traversal to identify the first node that does not have both left and right children. This node will be the next parent for insertion. Store these candidate parent nodes in a queue.
  • Insertion: When inserting a new node, check if the head of the queue has a left child. If not, insert the new node as the left child. Otherwise, insert it as the right child and remove the parent from the queue. If the new node is added as a right child, and the left child exists, add the new node to the queue as a possible future parent.
  • Root Access: The root of the tree is stored during initialization and can be returned directly.

• Time Complexity: O(1) for insert and get_root, O(N) for initialization, where N is the number of nodes in the tree. Space Complexity: O(W) where W is the maximum width of the tree, which in the worst case of a complete binary tree is O(N).

Code

    from collections import deque

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

class CBTInserter:

    def __init__(self, root: TreeNode):
        self.root = root
        self.queue = deque()
        q = deque([root])
        while q:
            node = q.popleft()
            if not node.left or not node.right:
                self.queue.append(node)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

    def insert(self, val: int) -> int:
        node = self.queue[0]
        new_node = TreeNode(val)
        if not node.left:
            node.left = new_node
        else:
            node.right = new_node
            self.queue.popleft()

        if node.left and node.right:
            pass
        else:
            self.queue.append(node)

        return node.val

    def get_root(self) -> TreeNode:
        return self.root