Skip to main content
Talentd

Trim a Binary Search Tree - Solution & Explanation

MediumTreeDepth-First SearchBinary Search TreeBinary Tree14 min readAsked at: Amazon, Adobe, Google +1
Practice this problem

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 lies 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. Note that the root may change depending on the given bounds.

 

Example 1:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

 

Constraints:

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

Approach Overview

Problem Overview: You receive the root of a binary search tree and two boundaries low and high. The task is to remove every node whose value falls outside this range while preserving the BST structure. The final tree must still satisfy the binary search tree property.

Approach 1: Recursive Trimming with BST Properties (O(n) time, O(h) space)

This approach directly uses the ordering guarantee of a BST. If a node value is smaller than low, the entire left subtree must also be smaller, so you skip it and continue trimming the right subtree. If a node value is greater than high, the entire right subtree can be discarded and you move to the left subtree. Otherwise the node is valid, so recursively trim both children and reconnect them. Each node is visited at most once using depth-first search, giving O(n) time where n is the number of nodes, and O(h) recursion stack space where h is the tree height.

Approach 2: Iterative Approach Using a Stack (O(n) time, O(h) space)

An iterative DFS avoids recursion by maintaining an explicit stack. First adjust the root until it falls within the valid range by moving right when the value is too small or left when it is too large. After fixing the root, traverse the tree with a stack and trim children in place. When a left child is below low, replace it with its right subtree; when a right child exceeds high, replace it with its left subtree. The algorithm still processes each node once, so the time complexity remains O(n). The stack holds at most O(h) nodes, matching the height of the tree.

Recommended for interviews: The recursive BST-based trimming solution is the expected answer in most interviews. It shows that you recognize how BST ordering lets you discard entire subtrees without scanning them individually. The iterative version is useful if the interviewer asks for a non-recursive DFS or wants to discuss stack-based tree traversal, but the recursive approach is usually shorter and easier to reason about under pressure.

Approach 1: Recursive Trimming with BST Properties

We can utilize the properties of a BST to perform a recursive traversal. The strategy here involves:

  • If the current node's value is less than low, we need to trim the left subtree and consider the right subtree.
  • If the current node's value is greater than high, we trim the right subtree and consider the left subtree.
  • If the current node's value is within the range [low, high], we recursively trim both subtrees.

The recursive function trimBST checks if the node is NULL. If the node's value is less than low, it trims the left subtree. If the node's value is greater than high, it trims the right subtree. Otherwise, it recursively processes both subtrees.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once.
Space Complexity: O(h), where h is the height of the tree, representing the recursion stack.

Try this approach in the editor →

Approach 2: Iterative Approach Using a Stack

This iterative approach uses a stack to traverse the tree. The main idea is to mimic the recursive depth-first search using an explicit stack.

  • Push the right child first to ensure the left child is processed first (since stack is LIFO).
  • Trim nodes from the stack if their values fall outside the [low, high] range.
  • Keep adjusting the left and right pointers based on the trimmed nodes.

Instead of using recursion, this C++ implementation uses a stack to perform depth-first search-like traversal. It adjusts the nodes based on their values compared to the bounds low and high, ensuring all nodes in the stack are within the bounds.

Code

C++JavaPython

C++

Java

Python

Complexity

Time Complexity: O(n), as each node is processed once.
Space Complexity: O(h), where h is the height of the tree, due to the stack usage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustJavaScriptC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Trimming with BST Properties

Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once.
Space Complexity: O(h), where h is the height of the tree, representing the recursion stack.

Iterative Approach Using a Stack

Time Complexity: O(n), as each node is processed once.
Space Complexity: O(h), where h is the height of the tree, due to the stack usage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Trimming with BST PropertiesO(n)O(h)Best general solution. Clean logic that leverages BST ordering to discard entire subtrees quickly.
Iterative DFS Using StackO(n)O(h)When recursion depth is a concern or the interviewer asks for an iterative tree traversal.

Video Solution

Trim a Binary Search Tree - Leetcode 669 - Python • NeetCode • 23,299 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Trim a Binary Search Tree easy or hard?
Trim a Binary Search Tree is classified as a Medium problem. The implementation is short, but recognizing that the BST property lets you discard entire subtrees without scanning them individually requires solid understanding of tree traversal and BST ordering.
Trim a Binary Search Tree Python/Java solution
In Python or Java, the typical solution is a recursive function that returns the trimmed subtree root. The function checks whether the current node is outside the range and recursively processes left and right children when the node is valid. This approach runs in O(n) time and O(h) space.
How to solve Trim a Binary Search Tree in O(n)?
Traverse the tree using DFS and leverage the BST property. If a node value is below the allowed range, return its right subtree; if it is above the range, return its left subtree. Otherwise recursively trim both children and reconnect them. Each node is processed once, producing an O(n) time solution.
What is the best approach for Trim a Binary Search Tree?
The recursive trimming approach that uses BST ordering is the most efficient and commonly expected solution. If a node value is less than low, its entire left subtree can be skipped; if it is greater than high, its right subtree can be skipped. This allows the algorithm to trim the tree with a single depth‑first traversal in O(n) time and O(h) space.
Is Trim a Binary Search Tree asked at Google/Amazon/Meta?
Binary search tree manipulation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations of tree pruning, subtree filtering, and BST property reasoning are common because they test recursion, DFS traversal, and understanding of tree invariants.
What data structure is used in Trim a Binary Search Tree?
The primary data structure is a binary search tree. The solution typically uses depth-first search traversal, either recursively or with an explicit stack, to examine nodes and remove subtrees that fall outside the allowed value range.
What is the time complexity of Trim a Binary Search Tree?
The time complexity is O(n) because every node in the tree is visited at most once during the trimming process. The space complexity is O(h), where h is the height of the tree, due to recursion stack or an explicit stack used for DFS traversal.

Ready to solve this problem?

Practice Trim a Binary Search Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II