> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-12-2022-669.-trim-a-binary-search-tree.md).

# 04/12/2022 669. Trim a Binary Search Tree

![](/files/WNUANQPTLwXBSNqbXOYH)

Method: in the BST, we konw the left subtree values are all less than the root val and right subtree value are greater than the root val. So in this question, we can first compare the root val with low and high. There are three cases: first, the root.val is less than low,  we can just ignore the root and left subtree as their values are all less than the low value. So we just return trimBST(root.right, low, high). Similarly, when the root.val> high, we can ignore the root and right subtree and just return trimBST(root.left, low, high). The last case is the root val is in the range. So we need to keep the root, and separately trim the left subtree and trim the right subtree.

Time O(N)

Space O(H)

```
// Some code
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {

        if (root == null) return root;
        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;
        
    }
}
```