Programming Interview Questions 26: Trim Binary Search Tree

Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree. So, if we get this tree as input:

and we’re given min value as 5 and max value as 13, then the resulting binary search tree should be:

We should remove all the nodes whose value is not between min and max. We can do this by performing a post-order traversal of the tree. We first process the left children, then right children, and finally the node itself. So we form the new tree bottom up, starting from the leaves towards the root. As a result while processing the node itself, both its left and right subtrees are valid trimmed binary search trees (may be NULL as well).

At each node we’ll return a reference based on its value, which will then be assigned to its parent’s left or right child pointer, depending on whether the current node is left or right child of the parent. If current node’s value is between min and max (min<=node<=max) then there’s no action need to be taken, so we return the reference to the node itself. If current node’s value is less than min, then we return the reference to its right subtree, and discard the left subtree. Because if a node’s value is less than min, then its left children are definitely less than min since this is a binary search tree. But its right children may or may not be less than min we can’t be sure, so we return the reference to it. Since we’re performing bottom-up post-order traversal, its right subtree is already a trimmed valid binary search tree (possibly NULL), and left subtree is definitely NULL because those nodes were surely less than min and they were eliminated during the post-order traversal. Remember that in post-order traversal we first process all the children of a node, and then finally the node itself.

Similar situation occurs when node’s value is greater than max, we now return the reference to its left subtree. Because if a node’s value is greater than max, then its right children are definitely greater than max. But its left children may or may not be greater than max. So we discard the right subtree and return the reference to the already valid left subtree. The code is easier to understand:

def trimBST(tree, minVal, maxVal):
if not tree:
return
tree.left=trimBST(tree.left, minVal, maxVal)
tree.right=trimBST(tree.right, minVal, maxVal)
if minVal<=tree.val<=maxVal:
return tree
if tree.val<minVal:
return tree.right
if tree.val>maxVal:
return tree.left

The complexity of this algorithm is O(N), where N is the number of nodes in the tree. Because we basically perform a post-order traversal of the tree, visiting each and every node one. This is optimal because we should visit every node at least once. This is a very elegant question that demonstrates the effectiveness of recursion in trees.

VN:F [1.9.11_1134]
Rating: 10.0/10 (1 vote cast)
Programming Interview Questions 26: Trim Binary Search Tree, 10.0 out of 10 based on 1 rating

This entry was posted in Programming Interview. Bookmark the permalink.

4 Responses to Programming Interview Questions 26: Trim Binary Search Tree

1. Sachin says:

If we do the condition checking before the recursive calls, we can avoid one unnecessary recursive call for the cases where tree.val > max and tree.val < min. When tree.val > max, we need to trim only the left subtree and vice versa.

• Arden says:

But note that we still have to destroy all that subtree, otherwise a memory leak will occur. So we can’t simply cut the link between the node and its child. In python code I don’t explicitly free the nodes, I just remove references to them and then the garbage collector performs the deletion itself. But I will update the article mentioning this case to avoid further confusion. Thanks for the comment, this is important to note.

2. Kowshik says:

It looks to me like there are null checks missing (or None checks in Python?).
Please see my comment inline below:

def trimBST(tree, minVal, maxVal):
if not tree:
return
tree.left=trimBST(tree.left, minVal, maxVal)
tree.right=trimBST(tree.right, minVal, maxVal)
##########
# Shouldn’t there be a check here on tree.left == None and tree.right == None
# before the comparisons below? This happens when leaf nodes are checked and
# the first line returns None viz:
#
# if not tree:
# return
##########
if minVal<=tree.val<=maxVal:
return tree
if tree.valmaxVal:
return tree.left

• Kowshik says:

Sorry, please ignore. It works fine!
Great question!