Log inSign up
mediumLeetCodeNot Started

Trim a Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

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 lie 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.

Constraints:

  • The number of nodes in the tree 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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master subtree bypass trimming via BST boundaries.
  • Prove why trimming preserves relative topological structure.
  • Implement the elegant 6-line recursive trimming solution.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Trim BST to boundary [low, high].
  • Preserve relative ancestor-descendant relationships.
  • Unique answer guaranteed.

Algorithmic Decision Tree:

  • root.val < low: bypass to root.right.
  • root.val > high: bypass to root.left.
  • In range: root.left = trim(root.left); root.right = trim(root.right); return root.

Connected Patterns:

Delete Node in a BSTRange Sum of BSTCount BST Nodes in a Given Range

1. Collect Valid Nodes & Reconstruct BST

Intuition

Perform an inorder traversal, filter elements between low and high, and construct a new BST. While all values are in range, this modifies tree topology and allocates O(N) memory, failing strict LeetCode structural validation.

When to apply: Baseline comparison (note: violates the relative structure preservation requirement).

Algorithm

  1. Collect all elements in range [low, high] into an array, and rebuild a balanced BST.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(TreeNode* root, int low, int high, std::vector<int>& vals) {
13 if (!root) return;
14 inorder(root->left, low, high, vals);
15 if (root->val >= low && root->val <= high) vals.push_back(root->val);
16 inorder(root->right, low, high, vals);
17 }
18
19 TreeNode* build(const std::vector<int>& vals, int l, int r) {
20 if (l > r) return nullptr;
21 int mid = l + (r - l) / 2;
22 TreeNode* node = new TreeNode(vals[mid]);
23 node->left = build(vals, l, mid - 1);
24 node->right = build(vals, mid + 1, r);
25 return node;
26 }
27public:
28 TreeNode* trimBST(TreeNode* root, int low, int high) {
29 std::vector<int> vals;
30 inorder(root, low, high, vals);
31 return build(vals, 0, (int)vals.size() - 1);
32 }
33};
34
35int main() {
36 TreeNode* root = new TreeNode(3);
37 root->left = new TreeNode(0);
38 root->right = new TreeNode(4);
39 root->left->right = new TreeNode(2);
40 root->left->right->left = new TreeNode(1);
41
42 Solution sol;
43 TreeNode* res = sol.trimBST(root, 1, 3);
44 std::cout << "Root: " << res->val << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Iterative Trimming (O(1) Auxiliary Space)

Intuition

1. Advance root: while root != null && (root.val < low || root.val > high), if root.val < low set root = root.right; else set root = root.left. 2. Trim left subtree: starting from root, follow curr.left. If curr.left.val < low, bypass curr.left = curr.left.right; else move curr = curr.left. 3. Trim right subtree: similarly bypass curr.right.val > high nodes with curr.right = curr.right.left. Runs in O(N) time and O(1) space.

When to apply: When strictly avoiding recursion call stack frames.

Algorithm

  1. First find the new root within [low, high], then iteratively trim the left and right subtrees.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* trimBST(TreeNode* root, int low, int high) {
13 if (!root) return nullptr;
14
15 // Find valid root
16 while (root && (root->val < low || root->val > high)) {
17 if (root->val < low) root = root->right;
18 else root = root->left;
19 }
20
21 // Trim left subtree
22 TreeNode* curr = root;
23 while (curr) {
24 while (curr->left && curr->left->val < low) {
25 curr->left = curr->left->right;
26 }
27 curr = curr->left;
28 }
29
30 // Trim right subtree
31 curr = root;
32 while (curr) {
33 while (curr->right && curr->right->val > high) {
34 curr->right = curr->right->left;
35 }
36 curr = curr->right;
37 }
38
39 return root;
40 }
41};
42
43int main() {
44 TreeNode* root = new TreeNode(3);
45 root->left = new TreeNode(0);
46 root->right = new TreeNode(4);
47 root->left->right = new TreeNode(2);
48 root->left->right->left = new TreeNode(1);
49
50 Solution sol;
51 TreeNode* res = sol.trimBST(root, 1, 3);
52 std::cout << "Root: " << res->val << " (Left: " << res->left->val << ")" << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) auxiliary space

3. Recursive BST Subtree Bypass (Gold Standard)

Intuition

1. Base case: if (!root) return null. 2. If root.val < low: root and its entire left subtree are out of bounds. Return trimBST(root.right, low, high). 3. If root.val > high: root and its entire right subtree are out of bounds. Return trimBST(root.left, low, high). 4. If low <= root.val <= high: retain root. Set root.left = trimBST(root.left, low, high) and root.right = trimBST(root.right, low, high). Return root.

When to apply: The definitive solution for technical interviews.

Algorithm

  1. Bypass out-of-range nodes recursively; return trimBST(root.right) if < low, trimBST(root.left) if > high.

Recursive BST Trimming Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Subtree roots are trimmed
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
root = 3: In range [1, 3] -> Retain 3. Recurse left (0) and right (4).
Decision / next transition
1
Why this step matters

Subtree roots are trimmed.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 TreeNode* trimBST(TreeNode* root, int low, int high) {
13 if (!root) return nullptr;
14
15 if (root->val < low) {
16 return trimBST(root->right, low, high);
17 }
18 if (root->val > high) {
19 return trimBST(root->left, low, high);
20 }
21
22 root->left = trimBST(root->left, low, high);
23 root->right = trimBST(root->right, low, high);
24 return root;
25 }
26};
27
28int main() {
29 TreeNode* root = new TreeNode(3);
30 root->left = new TreeNode(0);
31 root->right = new TreeNode(4);
32 root->left->right = new TreeNode(2);
33 root->left->right->left = new TreeNode(1);
34
35 Solution sol;
36 TreeNode* res = sol.trimBST(root, 1, 3);
37 std::cout << "Root: " << res->val << " (Left: " << res->left->val << ")" << std::endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Collect Valid Nodes & Reconstruct BSTO(N)O(N)Collect all elements in range [low, high] into an array, and rebuild a balanced BST.O(N)
2.Iterative Trimming (O(1) Auxiliary Space)O(N)O(1) auxiliary spaceFirst find the new root within [low, high], then iteratively trim the left and right subtrees.O(N)
3.Recursive BST Subtree Bypass (Gold Standard)OptimalO(N)O(H) recursion stack spaceBypass out-of-range nodes recursively; return trimBST(root.right) if < low, trimBST(root.left) if > high.O(N)

Common Pitfalls & Crucial Edge Cases

Rebuilding a balanced BST

Violates the problem requirement to keep descendant relationships unchanged.

Not assigning trimmed children

Calling trimBST(root.left, ...) without root.left = ... fails to update the tree.

Bypassing to wrong child

Returning trimBST(root.left) when root.val < low.

Crucial Edge Cases to Validate:

  • Entire tree is outside range (all nodes < low or > high) — Returns null.
  • Entire tree is within range — Tree remains completely unchanged.
  • Root is trimmed, but subtree remains — A descendant becomes the new root.
  • Single node tree in range — Returns root.
  • Single node tree out of range — Returns null.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize the bypass logic: 'If root.val < low, discard root and left subtree; return trim(root.right)'.
  2. Explain why the answer is mathematically unique.
  3. Highlight the clean 6-line recursive implementation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When root.val < low, why is it impossible for any node in root's left subtree to be part of the trimmed tree?

2.Does trimming a BST ever change the relative ancestor/descendant relationships of the nodes that remain?

3.What is the worst-case space complexity of the recursive trimming algorithm?

Back to DSA Sheet