Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Trim a Binary Search Tree solution and explanation

MediumBinary Search TreeBinary TreeDepth-First SearchTree5 min read66.9% acceptanceUpdated 9 Apr 2026
Asked atAdobeBloombergGoogleAmazon
Practise Trim a Binary Search Tree
11:53
Trim a Binary Search Tree - Leetcode 669 - PythonNeetCode · 11:53 · 23K viewsWatch on YouTube
9 more videos on this problem
  1. Trim a Binary Search Tree - Leetcode 669 - PythonNeetCode · 11:53 · 23K views
  2. Trim a Binary Search Tree | Live Coding with Explanation | Leetcode #669Algorithms Made Easy · 5:02 · 6K views
  3. Trim a Binary Search Tree | Leetcode 669 | BST | Day-15Ayushi Sharma · 13:52 · 4K views
  4. (Old) Leetcode 669 - BST, Recursion | Trim BSTNideesh Terapalli · 6:00 · 4K views
  5. Trim a Binary Search Tree || Leetcode 669 || Code + Explanation || C++Code with Alisha · 9:32 · 3K views
  6. Trim a Binary Search Tree | LeetCode 669 | bst treeNaresh Gupta · 10:11 · 1K views
  7. Trim a Binary Search Tree | Leetcode 669Coding Decoded · 9:22 · 1K views
  8. Leetcode - Trim a Binary Search Tree (Python)Timothy H Chang · 4:03 · 611 views
  9. Trim a Binary Search Tree | LeetCode 669 | Coders CampCoders Camp · 8:05 · 182 views
  10. Leetcode Medium: 669. Trim a Binary Search Treeleetcode · 7:39 · 138 views

The problem

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.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None
        if root.val < low:
            return self.trimBST(root.right, low, high)
        if root.val > high:
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public 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;
    }
}
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (!root) 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;
}
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var trimBST = function(root, low, high) {
    if (!root) 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;
};
#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {
    if (!root) 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;
}
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public 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;
    }
}

Python implementations directly return the recursive results based on the current node's value compared to the bounds.

Complexity

Time Complexity: O(n)
Space Complexity: O(h)

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.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        while root and (root.val < low or root.val > high):
            root = root.right if root.val < low else root.left

        if not root:
            return None

        stack = []
        current = root

        while current or stack:
            while current:
                if low <= current.val <= high:
                    stack.append(current)
                    current = current.left
                else:
                    current = current.right if current.val < low else current.left
            if stack:
                current = stack.pop().right

        return root
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        while (root != null && (root.val < low || root.val > high)) {
            root = (root.val < low) ? root.right : root.left;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                if (low <= current.val && current.val <= high) {
                    stack.push(current);
                    current = current.left;
                } else {
                    current = (current.val < low) ? current.right : current.left;
                }
            }
            if (!stack.isEmpty()) {
                current = stack.pop().right;
            }
        }
        return root;
    }
}
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (!root) return NULL;
    while (root && (root->val < low || root->val > high)) {
        root = root->val < low ? root->right : root->left;
    }
    TreeNode* current = root;
    stack<TreeNode*> nodeStack;
    while (current || !nodeStack.empty()) {
        while (current) {
            if (current->val >= low && current->val <= high) {
                nodeStack.push(current);
                current = current->left;
            } else {
                current = current->val < low ? current->right : current->left;
            }
        }
        if (!nodeStack.empty()) {
            current = nodeStack.top()->right;
            nodeStack.pop();
        }
    }
    return root;
}

The Python solution employs a stack for an iterative node traversal. Adjustments are made according to the node values relative to low and high. Nodes are appended to a stack for traversal if they are valid.

Complexity

Time Complexity: O(n)
Space Complexity: O(h)

Try this approach in the editor

Approach 3: Default Approach

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
    const dfs = (root: TreeNode | null) => {
        if (root == null) {
            return root;
        }
        const { val, left, right } = root;
        if (val < low || val > high) {
            return dfs(left) || dfs(right);
        }
        root.left = dfs(left);
        root.right = dfs(right);
        return root;
    };
    return dfs(root);
}
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func trimBST(root *TreeNode, low int, high int) *TreeNode {
	if root == nil {
		return root
	}
	if root.Val > high {
		return trimBST(root.Left, low, high)
	}
	if root.Val < low {
		return trimBST(root.Right, low, high)
	}
	root.Left = trimBST(root.Left, low, high)
	root.Right = trimBST(root.Right, low, high)
	return root
}
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn trim_bst(
        mut root: Option<Rc<RefCell<TreeNode>>>,
        low: i32,
        high: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if root.is_none() {
            return root;
        }
        {
            let mut node = root.as_mut().unwrap().borrow_mut();
            if node.val < low {
                return Self::trim_bst(node.right.take(), low, high);
            }
            if node.val > high {
                return Self::trim_bst(node.left.take(), low, high);
            }
            node.left = Self::trim_bst(node.left.take(), low, high);
            node.right = Self::trim_bst(node.right.take(), low, high);
        }
        root
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Trimming with BST Properties

Time Complexity: O(n)
Space Complexity: O(h)

Iterative Approach Using a Stack

Time Complexity: O(n)
Space Complexity: O(h)

Default Approach–

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.

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.

Comments

Now write it yourselfClose this page and solve Trim a Binary Search Tree in the editor, without looking.
Practise Trim a Binary Search Tree