# Solution by awice

• #### 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.

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