Skip to content

669. Trim a Binary Search Tree 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  TreeNode* trimBST(TreeNode* root, int L, int R) {
    if (root == nullptr)
      return nullptr;
    if (root->val < L)
      return trimBST(root->right, L, R);
    if (root->val > R)
      return trimBST(root->left, L, R);
    root->left = trimBST(root->left, L, R);
    root->right = trimBST(root->right, L, R);
    return root;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
  }
}