Approach #1: Recursion [Accepted]
Intuition
Let trim(node)
be the desired answer for the subtree at that node. We can construct the answer recursively.
Algorithm
When node.val > R
, we know the trimmed binary tree must occur to the left of the node. Similarly, when node.val < L
, the trimmed binary tree occurs to the right of the node. Otherwise, we will trim both sides of the tree.
Java
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return root;
if (root.val > R) return trimBST(root.left, L, R);
if (root.val < L) return trimBST(root.right, L, R);
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
}
Python
class Solution(object):
def trimBST(self, root, L, R):
def trim(node):
if not node:
return None
elif node.val > R:
return trim(node.left)
elif node.val < L:
return trim(node.right)
else:
node.left = trim(node.left)
node.right = trim(node.right)
return node
return trim(root)
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the total number of nodes in the given tree. We visit each node at most once.

Space Complexity: $$O(N)$$. Even though we don't explicitly use any additional memory, the call stack of our recursion could be as large as the number of nodes in the worst case.