# 669. Trim a Binary Search Tree

###### tags: `leetcode`,`BST`,`medium`

>ref: https://leetcode.com/problems/trim-a-binary-search-tree/
>
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.




>1. timeCom(n) 除了上下限外,介於中間的node需輪走一遍,spatialCom(1) 不須額外空間

    public TreeNode trimBST(TreeNode root, int low, int high) {
        
        if(root==null) return null;
        
        if(root.val > high) return trimBST(root.left,low,high); //discard right side, ride side must large than high
        if(root.val < low) return trimBST(root.right,low,high); //discard left side, left side must smaller than low
        
        root.left= trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);
        
        return root;
    }