Trim a Binary Search Tree
Medium · Graphs · Explanation and code example
Iterative DFS (Optimal)
How it works
Instead of using a stack, we can trim the tree in two linear passes. After finding a valid root, we traverse down the left spine fixing any nodes that fall below low, then traverse down the right spine fixing any nodes that exceed high. This works because in a BST, once we fix a node on one side, we only need to continue checking in that direction.
Steps
- Find a valid root by skipping nodes outside the range.
- Save the valid root as
tmpRoot. - Traverse the left spine: while there is a left child with value less than
low, replace it with its right child. Move to the next left child. - Reset to
tmpRootand traverse the right spine: while there is a right child with value greater thanhigh, replace it with its left child. Move to the next right child. - Return
tmpRoot.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)extra space.
Things to watch for
Forgetting to Recursively Trim After Skipping a Node
When a node's value is outside the range and you skip to its child, you must continue trimming that child subtree. A common mistake is to simply return the child without recursively processing it. The child itself or its descendants may also be outside the valid range and need trimming.
Confusing Which Subtree to Keep When Node is Out of Range
When a node's value is greater than high, you should return the trimmed left subtree (not the right). When a node's value is less than low, you should return the trimmed right subtree (not the left). Mixing these up violates the BST property and produces incorrect results.
Not Handling the Case Where the Root Itself is Invalid
The root node may be outside the [low, high] range, meaning the entire original root gets discarded. A common oversight is assuming the root will always be valid. Your solution must handle finding a new valid root by traversing into the appropriate subtree before beginning the main trimming logic.
Python code example
from typing import Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
while root and (root.val < low or root.val > high):
root = root.right if root.val < low else root.left
tmpRoot = root
while root:
while root.left and root.left.val < low:
root.left = root.left.right
root = root.left
root = tmpRoot
while root:
while root.right and root.right.val > high:
root.right = root.right.left
root = root.right
return tmpRoot
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
while (root && (root->val < low || root->val > high)) {
root = (root->val < low) ? root->right : root->left;
}
TreeNode* tmpRoot = root;
while (root) {
while (root->left && root->left->val < low) {
root->left = root->left->right;
}
root = root->left;
}
root = tmpRoot;
while (root) {
while (root->right && root->right->val > high) {
root->right = root->right->left;
}
root = root->right;
}
return tmpRoot;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.