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.