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.

Description Solution Video 11:53

669. Trim a Binary Search Tree

Medium66.9% acceptance4 companies

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, 10⁴].
0 <= Node.val <= 10⁴
The value of each node in the tree is unique.
root is guaranteed to be a valid binary search tree.
0 <= low <= high <= 10⁴

Asked at 4 companies

Adobe Bloomberg

Google Amazon

Topics

11:53

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,0,2]
1
2

Input

[3,0,4,null,2,null,null,1]
1
3

Your code is saved on this device.Solution