Trim A Binary Search Tree - Leetcode Solution

Problem Description:

Given the root of a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example:

Input: 1 /
0 2

L = 1 R = 2

Output: 1
2

Solution:

The solution to this problem involves trimming the binary search tree such that it only contains elements within the range [L, R]. The process begins with the root node of the tree. If the root node value is less than L, we discard the left subtree since it doesn’t contain any node within the range [L, R], and focus only on the right subtree.

On the other hand, if the root node value is greater than R, we discard the right subtree since it doesn’t have any node guaranteeing that it lies within the range [L, R], and focus only on the left subtree. In either case, we recursively pass the left or right subtree as the new root for further trimming.

The code below outlines the procedure for trimming the binary search tree.

def trim_BST(root, L, R):
  # Base Case
  if not root:
    return None

  # Recursively Trim Left Subtree
  if root.val > R:
    return trim_BST(root.left, L, R)

  # Recursively Trim Right Subtree
  if root.val < L:
    return trim_BST(root.right, L, R)

  # Recursively Trim Left And Right Subtrees
  root.left = trim_BST(root.left, L, R)
  root.right = trim_BST(root.right, L, R)

  return root

The recursive function trim_BST has three conditions for trimming the binary search tree.

1. If the node value is greater than R, we recursively trim the left subtree since it does not contain any node within the range [L,R]. We return the left trimmed tree.

2. If the node value is less than L, we recursively trim the right subtree since it does not contain any node within the range [L,R]. We return the right trimmed tree.

3. If the node value is within the range [L,R], we recursively trim both left and right subtrees for the current root node, and return the trimmed tree containing the root.

Finally, we call the recursive function with the root of the tree, L and R as arguments.

trimmed = trim_BST(root, L, R)

The output will be the new root node of the trimmed binary search tree.

1