# Solution by pingu92

• #### Approach #1 Recursive Tree Traversal [Accepted]

Intuition

Given tree is binary search tree (BST, read more here: https://en.wikipedia.org/wiki/Binary_search_tree) that has a special property that left node has a value smaller than the root and right node has a value greater than the root.
Our main task here is to limit the values of the tree in the given range defined by values `L` and `R`.

Algorithm

Suppose we have a function `def trimBST(self, root, L, R):`, we can recurse on the root. At any time if `node.val < L` we simply ignore this node and move to right subtree of the node. Similarly, at any time if `node.val > R` we ignore this node and move to left subtree of the node. If the value belongs in the range `L < node.val < R` then we recurse on both the subtree of the node.

Python

``````def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if root is not None:
if root.val > R: # ignore the right subtree
return self.trimBST(root.left, L, R)
elif root.val < L: # ignore the left subtree
return self.trimBST(root.right, L, R)
else:
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
return root
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$. Where n is the number of nodes in the tree.
Since we traverse the entire tree just once, the complexity is \$\$O(n)\$\$.

• Space complexity : \$\$O(n)\$\$ due to recursion.

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