Question

link

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.

Input:

With min value as 5 and max value as 13, the output is:

Analysis

There is a good analysis from geeksforgeeks:

1. If value of root’s key is greater than k1, then recursively call in left subtree.
2. If value of root’s key is in range, then print the root’s key.
3. If value of root’s key is smaller than k2, then recursively call in right subtree.

Another great solution is from Arden Dertat.

Code

First code, from geeksforgeeks - print the result instead of return.

void Print(struct node *root, int k1, int k2)
{
   if ( NULL == root )
      return;
   if ( k1 < root->data )
     Print(root->left, k1, k2);
   if ( k1 <= root->data && k2 >= root->data )
     printf("%d ", root->data );
   if ( k2 > root->data )
     Print(root->right, k1, k2);
}

Second code from Arden:

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