Trim a Binary Search Tree

Difficulty Level Easy
Frequently asked in Samsung
Binary Search Tree Binary Tree TreeViews 3077

In Trim a Binary Search Tree problem we have given a binary search tree and a lower (as L) and higher bound (as R) of a range of integer values, trim the BST so that all its elements lie in the range[L,R] (R >= L). If the given BST root value doesn’t lie in the range, then a new root with value in the given range is to be returned.

Example

Input: L = 6, R = 8

Trim a Binary Search Tree

as we observe that all the values not within the range[6,8] are removed from the BST and a new BST rooted at 6 is obtained.

Input: L = 3, R = 5Trim a Binary Search Tree

Input: L = 2, R = 6

Trim a Binary Search Tree

Types of solution

  1. Recursive postorder traversal.
  2. Iterative preorder traversal.

Recursive postorder traversal

Approach

The idea is to perform a postorder traversal, recursively trim the left and right subtree in the range[L, R] of the given tree root using the function trimBST(), after which the root node is processed, consider the following:

  1. if the root node has a value greater than R, return the left child of the root.
  2. Else if the root node has value less than L, return the right child of the root.
  3. Else if root node value lies in the range [L, R], there’s no need to change the root.

Process 1 or 2 will definitely return a tree node whose value lies in the range[L, R] as we had already recursively trimmed the left and right subtrees of the root node.

Algorithm

  1. Define recursive function trimBST().
  2. Return null if the tree is empty.
  3. trim left subtree recursively.
  4. trim right subtree recursively.
  5. Consider the root node.
    • if the root node is in the range[L, R], return it as it is.
    • else if root node value is less than L, return root.right.
    • else if root node value is greater than R, return root.left.

Implementation for Trim a Binary Search Tree

C++ Program

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* structure of a tree node */
class TreeNode
{
    public:
    
    int data;
    TreeNode *left;
    TreeNode *right;
    
    TreeNode(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/* function to trim the BST */
TreeNode *trimBST(TreeNode *root,int L,int R)
{
    if (root == NULL) 
    return root;
    
    root->left = trimBST(root->left,L,R);
    root->right = trimBST(root->right,L,R);
    
    if(root->data < L || root->data > R)
    {
        if(root->left == NULL)
        return root->right;
        
        if(root->right == NULL)
        return root->left;
    }
    
    return root;
}

/* function to perform inorder traversal of the BST */
static void inorder(TreeNode *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main() 
{
    /* construct the BST */
    TreeNode *root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);
    
    cout<<"Inorder Traversal Without Trimming: ";
    inorder(root);
    
    /* define the upper and lower bound of the 
    ranges into which the BST needs to be trimmed */
    int L = 2;
    int R = 6;
    
    root = trimBST(root,L,R);
    cout<<endl;
    
    cout<<"Inorder Traversal After Trimming: ";
    inorder(root);

  return 0;
}
Inorder Traversal Without Trimming: 1 2 3 4 5 6 7 
Inorder Traversal After Trimming: 2 3 4 5 6

Java Program

import java.io.*;
import java.util.*;

class TutorialCup 
{
    /* structure of a tree node */
    static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int num)
        {
            data = num;
            left = right = null;
        }
    }
    
    /* function to trim the BST */
    static TreeNode trimBST(TreeNode root,int L,int R)
    {
        if (root == null) 
        return root;
        
        root.left = trimBST(root.left,L,R);
        root.right = trimBST(root.right,L,R);
        
        if(root.data < L || root.data > R)
        {
            if(root.left == null)
            return root.right;
            
            if(root.right == null)
            return root.left;
        }
        
        return root;
    }
    
    /* function to perform inorder traversal of the BST */
    static void inorder(TreeNode root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }

  public static void main (String[] args) 
  {
      /* construct the BST */
    TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        
        System.out.print("Inorder Traversal Without Trimming: ");
        inorder(root);
        
        /* define the upper and lower bound of the 
        ranges into which the BST needs to be trimmed */
        int L = 2;
        int R = 6;
        
        root = trimBST(root,L,R);
        System.out.println();
        
        System.out.print("Inorder Traversal After Trimming: ");
        inorder(root);
  }
}
Inorder Traversal Without Trimming: 1 2 3 4 5 6 7 
Inorder Traversal After Trimming: 2 3 4 5 6

Complexity Analysis for Trim a Binary Search Tree

  1. Time Complexity: T(n) = O(n).
  2. Space Complexity: A(n) = O(1).

n = number of nodes in the BST.

Iterative preorder traversal

Approach

The idea is to somehow convert the iterative code into recursive code, this is done by performing an iterative preorder traversal using the stack data structure. The root node is processed before the children node. The algorithm is discussed below.

Algorithm

  1. Define a function findValidRoot() which takes the tree root node and does the following:
    1. if root node value is in the range[L, R], simply return the root node.
    2. else if root node value is less than L, look for a nearest inorder successor (in right subtree) of the root node that has value in the range[L, R] and return the node so found.
    3. else if root node value is greater than L, look for nearest inorder predecessor (in left subtree) of the root node that has value in the range[L, R] and return the node so found.
    4. The node returned by findValidroot() is the new root of the trimmed BST.
  2. Define a stack for performing DFS traversal.
  3. Push the new root node into the stack and begin traversal.
  4. Inside traversal, pop a node, push it’s left and right children(if present) into the stack.
  5. if the popped node has left children whose value is less than L, the find the inorder successor of this children and assign it as left children of the popped node.
  6. if the popped node has right children whose value is greater than R, the find inorder predecessor of this children and assign it as right children of the popped node.
  7. After the traversal is over, return the root node.

Implementation for Trim a Binary Search Tree

C++ Program

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* structure of a tree node */
class TreeNode
{
    public:
    
    int data;
    TreeNode *left;
    TreeNode *right;
    
    TreeNode(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/* function that returns the new root for the 
trimmed BST with it's value in range[L,R] */
TreeNode *findValidRoot(TreeNode *root, int L, int R)
{
    while(root->data < L || root->data > R)
    {
        if(root->data < L)
            root = root->right;
            
        if(root->data > R)
            root = root->left;
    }
    
    return root;
}

/* function to trim the BST */
TreeNode *trimBST(TreeNode *root,int L,int R)
{
    if (root == NULL) 
    return root;
    
    /* create a stack for DFS traversal */
    stack <TreeNode*> Stack;
    
    /* 
    if the given root value doesn't lie in range[L,R], 
        either of two cases arise:
        
        root value is less than L -> look for the inorder 
            successor of root whose value is in range[L,R]
        root value is more than R -> look for the inorder 
            predecessor of root whose value is in range[L,R]
            
        The new node obtained above should be 
        the new root of the timmed BST
    */
    root = findValidRoot(root, L, R);
    Stack.push(root);
    
    /* begin DFS traversal */
    while(!Stack.empty())
    {
        TreeNode *current = Stack.top();
        Stack.pop();
        
        if(current != NULL)
        {
            if (current->left != NULL) 
            Stack.push(current->left);
            if (current->right != NULL) 
            Stack.push(current->right);
            
            while(current->left != NULL && current->left->data < L)
                current->left = current->left->right;
            
            while(current->right != NULL && current->right->data > R)
                current->right = current->right->left;
        }
    }
    
    return root;
}

/* function to perform inorder traversal of the BST */
static void inorder(TreeNode *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main() 
{
    /* construct the BST */
    TreeNode *root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);
    
    cout<<"Inorder Traversal Without Trimming: ";
    inorder(root);
    
    /* define the upper and lower bound of the 
    ranges into which the BST needs to be trimmed */
    int L = 2;
    int R = 6;
    
    root = trimBST(root,L,R);
    cout<<endl;
    
    cout<<"Inorder Traversal After Trimming: ";
    inorder(root);

  return 0;
}
Inorder Traversal Without Trimming: 1 2 3 4 5 6 7 
Inorder Traversal After Trimming: 2 3 4 5 6

Java Program

import java.io.*;
import java.util.*;

class TutorialCup 
{
    /* structure of a tree node */
    static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int num)
        {
            data = num;
            left = right = null;
        }
    }
    
    /* function that returns the new root for the 
    trimmed BST with it's value in range[L,R] */
    static TreeNode findValidRoot(TreeNode root, int L, int R)
    {
        while(root.data < L || root.data > R)
        {
            if(root.data < L)
                root = root.right;
                
            if(root.data > R)
                root = root.left;
        }
        
        return root;
    }
    
    /* function to trim the BST */
    static TreeNode trimBST(TreeNode root,int L,int R)
    {
        if (root == null) 
        return root;
        
        /* create a stack for DFS traversal */
        Stack<TreeNode> stack = new Stack<>();
        
        /* 
        if the given root value doesn't lie in range[L,R], 
            either of two cases arise:
            
            root value is less than L -> look for the inorder 
                successor of root whose value is in range[L,R]
            root value is more than R -> look for the inorder 
                predecessor of root whose value is in range[L,R]
                
            The new node obtained above should be 
            the new root of the timmed BST
        */
        root = findValidRoot(root, L, R);
        stack.push(root);
        
        /* begin DFS traversal */
        while(!stack.isEmpty())
        {
            TreeNode current = stack.pop();
            if(current!=null)
            {
                if (current.left!=null) 
                stack.push(current.left);
                if (current.right!=null) 
                stack.push(current.right);
                
                while(current.left!=null && current.left.data < L)
                    current.left = current.left.right;
                
                while(current.right!=null && current.right.data > R)
                    current.right = current.right.left;
            }
        }
        
        return root;
    }
    
    /* function to perform inorder traversal of the BST */
    static void inorder(TreeNode root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }

  public static void main (String[] args) 
  {
      /* construct the BST */
    TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        
        System.out.print("Inorder Traversal Without Trimming: ");
        inorder(root);
        
        /* define the upper and lower bound of the 
        ranges into which the BST needs to be trimmed */
        int L = 2;
        int R = 6;
        
        root = trimBST(root,L,R);
        System.out.println();
        
        System.out.print("Inorder Traversal After Trimming: ");
        inorder(root);
  }
}
Inorder Traversal Without Trimming: 1 2 3 4 5 6 7 
Inorder Traversal After Trimming: 2 3 4 5 6

Complexity Analysis for Trim a Binary Search Tree

  1. Time Complexity: T(n) = O(n).
  2. Space Complexity: A(n) = O(n), stack space used.

n = number of nodes in the BST.

References

Translate ยป