Introduction

In this blog post, we will explore how to solve the LeetCode problem "669" 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

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer. Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds. Example 1: Input: root = [1,0,2], low = 1, high = 2 Output: [1,null,2] Example 2: Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3 Output: [3,2,null,1] Constraints: The number of nodes in the tree is in the range [1, 104]. 0 <= Node.val <= 104 The value of each node in the tree is unique. root is guaranteed to be a valid binary search tree. 0 <= low <= high <= 104

Explanation

Here's the solution:

• Recursive Approach: The core idea is to use recursion to traverse the BST. For each node, we check if its value is within the range [low, high].
• Trimming Logic:
  • If the node's value is less than low, then the entire left subtree is smaller than low and therefore irrelevant. We return the result of trimming the right subtree.
  • If the node's value is greater than high, then the entire right subtree is larger than high and therefore irrelevant. We return the result of trimming the left subtree.
  • If the node's value is within the range, we recursively trim both the left and right subtrees and return the node itself.

• BST Property Preservation: This approach naturally preserves the BST property as we are only discarding subtrees that are entirely outside the range.

• Runtime Complexity: O(N), where N is the number of nodes in the BST.

• Storage Complexity: O(H), where H is the height of the BST, due to the recursion stack. In the worst case (skewed tree), H = N, and in the best case (balanced tree), H = logN.

Code

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

def trimBST(root: TreeNode, low: int, high: int) -> TreeNode:
    if not root:
        return None

    if root.val < low:
        return trimBST(root.right, low, high)
    elif root.val > high:
        return trimBST(root.left, low, high)
    else:
        root.left = trimBST(root.left, low, high)
        root.right = trimBST(root.right, low, high)
        return root