How do you solve Trim a Binary Search Tree on LeetCode?

Trim a Binary Search Tree (LeetCode #669) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Utilize the properties of BST for efficient trimming.

What is the brute force solution for Trim a Binary Search Tree?

The brute force approach for Trim a Binary Search Tree is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute-force approach involves traversing the entire tree and collecting all the nodes that fall within the specified range. After collecting, we can reconstruct the tree with only those nodes. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Trim a Binary Search Tree?

Trim a Binary Search Tree uses the following concepts: Tree, Depth-First Search, Binary Search Tree, Binary Tree. The recommended patterns to study are: Recursion, Tree Traversal.

What are the interview tips for Trim a Binary Search Tree?

Explain your thought process clearly while coding. Consider edge cases and test them with examples. Discuss time and space complexity as you go.

What are common mistakes when solving Trim a Binary Search Tree?

Not considering the case when the root itself is out of bounds. Failing to handle null nodes properly.

#669

Trim a Binary Search Tree

Medium

TreeDepth-First SearchBinary Search TreeBinary TreeRecursionTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach leverages the properties of a binary search tree (BST) to trim the tree in a single traversal. By recursively checking each node, we can decide whether to keep it or trim it based on its value relative to the given bounds.

⚙️

Algorithm

4 steps

1Step 1: If the current node is null, return null.
2Step 2: If the current node's value is less than low, recursively trim the right subtree.
3Step 3: If the current node's value is greater than high, recursively trim the left subtree.
4Step 4: If the current node's value is within the range, recursively trim both subtrees and return the current node.

solution.py19 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
10        if not root:
11            return None
12        if root.val < low:
13            return self.trimBST(root.right, low, high)
14        elif root.val > high:
15            return self.trimBST(root.left, low, high)
16        else:
17            root.left = self.trimBST(root.left, low, high)
18            root.right = self.trimBST(root.right, low, high)
19            return root

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Utilize the properties of BST for efficient trimming.
2Recursive solutions can often simplify tree problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.