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.22_1171]
Rating: 8.3/10 (60 votes cast)
Programming Interview Questions 26: Trim Binary Search Tree, 8.3 out of 10 based on 60 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
  • Sachin

    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

      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.

      • Anonymous Coward

        I agree with Sachin. In Python/Java/C#, you can rely on the garbage collector to collect the entire subtree that you trimmed, making it so you don’t have to visit subtrees that are obviously out of range.

    • Sree Hari

      Suppose root is 10,
      Root->left is 3,
      Root->left->right is 8.
      Now range is (5,15)
      If we delete root->left by checking 3 <5. We'll lose 8 which is greater than 5

  • Kowshik

    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

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

  • kewal

    why not use a top down approach here ?
    by doin that we can skip the entire left sub tree whenever we come across a value smaller and right subtree whenever we come across a value which is larger..
    for example: in the tree given above , when the pointer comes to 3, there is no need for it to go and check 1, it can directly eliminate the whole left subtree.
    so eventhough its an O(N) solution only,wont this be better ?

    • holdnet

      Yes u are right, I was thinking the same way.

    • Sree Hari

      Suppose root is 10,
      Root->left is 3,
      Root->left->right is 8.
      Now range is (5,15)
      If we delete root->left by checking 3 <5. We'll lose 8 which is greater than 5.

  • sonesh

    I don’t think the solution is correct..???
    IT is very essay to gind the fault , just consider two level tree and you will see the fault.

  • EY

    You can do without the extra comparisons since the in-range logic is implied after checking the two bounds:

    if tree.valmaxVal:
    return tree.left
    return tree

    • EY

      You can do without the extra comparisons since the in-range logic is implied after checking the two bounds:

          if tree.valmaxVal:
              return tree.left
          return tree
      
  • Sean

    HI Arden:

    Thanks for sharing all these interview questions. I want to ask which tool did you use to draw all the graphs(like BST in this post) in your posts?

    Thx!

  • Lau Chok Sheak

    public Tree trimTree(Tree root, int min, int max) {
    if (root == null) return null;
    if (root.value max) return trimTree(root.left, min, max);
    root.left = trimTree(root.left, min, max);
    root.right = trimTree(root.right, min, max);
    }

  • madno

    We can return when the range covered by the tree is inside min max:

    static TreeNode trim(TreeNode node, int min, int max){
    if (min > max){
    int tmp = min;
    min = max;
    max = tmp;
    }
    return trim(node, min, max, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    static TreeNode trim(TreeNode node, int min, int max, int treeRangeMin, int treeRangeMax){
    if (node == null) { return null; }
    if (min <= treeRangeMin && treeRangeMax <= max) { return node; }
    if (node.val max) { return trim(node.l, min, max, treeRangeMin, node.val); }
    node.l = trim(node.l, min, max, treeRangeMin, node.val);
    node.r = trim(node.r, min, max, node.val, treeRangeMax);
    return node;
    }