Trim a Binary Search Tree Solution in Java

class Solution {
  public TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null)
      return null;
    if (root.val < low)
      return trimBST(root.right, low, high);
    if (root.val > high)
      return trimBST(root.left, low, high);
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
  }
}
    

Problem Description

So, you’ve got a Binary Search Tree (BST) that’s a bit too wild for your taste. It’s like that one friend who just can’t stop talking about their latest conspiracy theory. You want to trim it down to a more manageable size, keeping only the nodes that fall within a certain range. Think of it as a digital gardening session where you’re pruning away the branches that are just too out there.

In LeetCode terms, the problem is to trim a BST so that all its elements lie within a given range [low, high]. If a node’s value is less than low, you discard it and keep its right subtree. If it’s greater than high, you discard it and keep its left subtree. Easy peasy, right?

Approach

The approach here is recursive. You start at the root and check if it falls within the specified range. If it doesn’t, you decide whether to go left or right based on its value. If it’s within the range, you recursively trim both the left and right subtrees. It’s like a digital bouncer at a club, only letting the right people in!

Time and Space Complexity

Time Complexity

O(N), where N is the number of nodes in the tree. In the worst case, we might have to visit every node.

Space Complexity

O(H), where H is the height of the tree. This is due to the recursion stack.

Real-World Example

Imagine you’re at a party, and you only want to talk to people who are between the ages of 25 and 35. You start at the entrance (the root of the BST) and check each person’s age. If they’re too young, you send them to the right (the older crowd), and if they’re too old, you send them to the left (the younger crowd). Eventually, you end up with a nice group of people to chat with, just like trimming your BST!