# C++ Solution 16ms (with intuition + explanation)

• Intuition
Recursively trim the left and right sides, and return the root.

Edge Cases
The edge cases are when the root itself falls outside the boundary. There are two possibilities: it falls out on the left side (root value is less than `L`) or it falls out on the right side (root value is greater than `R`). In these cases, we can just "promote" the opposite child up as the new root, after applying the recursive `trimBST` call on the child.
Why can we do this? If the root value is less than `L`, then we know everything on the left side is also less than `L` by property of binary search tree; it follows that we can "throw away" everything on the left side. The same follows for the opposite case.

Algorithm

``````    TreeNode* trimBST(TreeNode* root, int L, int R) {
if (!root) 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;
}
``````

Complexity Analysis
This solution also short-circuits and makes sure we don't make 2 recursive calls when unnecessary.
Regardless, in the worst case, we hit every node once, so we run in `O(n)` for `n` nodes in the tree.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.