Trim a Binary Search Tree — Solution in Python, Java & C++
Trim a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Trim a Binary Search Tree is a medium coding problem on depth-first search, trees and recursion, asked in Amazon, Microsoft and Bloomberg interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees, Recursion
- Asked at: Amazon, Microsoft, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree with distinct values and two integers low and high. Trim the tree so that every remaining value lies in the inclusive range [low, high].
Trimming must not change the relative structure of the nodes that remain: any node that stays keeps every remaining descendant as a descendant. The result is unique. Return the root of the trimmed tree, which may be different from the original root, or an empty tree.
Example 1
Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
Explanation: 0 is below the range and is removed; 1 and 2 stay where they were.
Example 2
Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]
Explanation: 0 is too small, so its right subtree (2 with child 1) takes its place under 3; 4 is too large and has no children to keep.
Example 3
Input: root = [2,1,3], low = 4, high = 5
Output: []
Explanation: Every value is below 4, so nothing survives.
Constraints
The number of nodes in the tree is in the range [1, 10^4]0 <= Node.val <= 10^4The value of each node in the tree is uniqueroot is guaranteed to be a valid binary search tree0 <= low <= high <= 10^4
Hints for Trim a Binary Search Tree
Hint 1
If a node's value is below
low, the node and its entire left subtree are belowlowtoo.Hint 2
So for such a node, the answer is simply the trimmed version of its right subtree — and symmetrically for a value above
high.Hint 3
A node inside the range stays: trim its two subtrees recursively and reattach the results.
How to solve Trim a Binary Search Tree
The search-tree order lets a whole subtree be discarded at once: a node below low drags its left subtree with it, a node above high its right subtree. A recursive function that returns the trimmed root of any subtree expresses this directly.
Approach
trim(node): ifnodeis null, return null.- If
node.val < low, returntrim(node.right). - If
node.val > high, returntrim(node.left). - Otherwise set
node.left = trim(node.left)andnode.right = trim(node.right), and returnnode.
Why it works
Every node in the left subtree of a node below low is smaller still, so none of them can remain; the trimmed right subtree, whose values are all greater than that node, takes its place under the same parent and keeps the order. In-range nodes keep their position and recurse, so remaining nodes keep their ancestor relations.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion
Pitfalls
- A node out of range is not simply deleted: its valid subtree must be spliced into its place.
- The root itself can be out of range — the new root is whatever the recursion returns.
- The result can be empty.
Reference solution
Python
from typing import Optional
def trimBST(root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if root is None:
return None
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 rootJava
public static 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;
}C++
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (!root) return nullptr;
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;
}JavaScript
var trimBST = function(root, low, 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;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals