C++ Pruning BSTs : write a method/function that prunes a BST by “deleting” nodes

Question

C++

Pruning BSTs: write a method/function that prunes a BST by “deleting” nodes with key values out of a given range [min, max]. Since actual deletions of nodes from BST is expensive (O(h) time for BSTs of height h) and also some applications might require fast recovery of deleted nodes, we will just put “deletion marks” on those nodes instead of actually deleting them. There are two types of marks we can use to mark nodes: (1) type-I marks indicating that the marked nodes are unavailable (“deleted”); and (2) type-II marks indicating that all nodes in the subtree rooted at the marked nodes are unavailable (“deleted”). There is an O(h)-time algorithm that places no more than O(h) marks (type-I and type-II combined) in a BST of height h in order to indicate that all nodes with key values outside a given range [min, max] are unavailable. One possible application of such an algorithm is that in implementing a shopping website, we might need to use BSTs to store results of a search and facilitate fast refinement of the search results, i.e., tablets within a price range.

Explanation / Answer

Consider a price range between 0 -13$,

Program

// A C++ program to remove BST keys outside the given range

#include<stdio.h>

#include <iostream>

using namespace std;

// A BST node has key, and left and right pointers

struct node

{

    int key;

    struct node *left;

    struct node *right;

};

// Resmoves all nodes having value outside the given range and returns the root

// of modified tree

node* removeOutsideRange(node *root, int min, int max)

{

   // Base Case

   if (root == NULL)

      return NULL;

   // First fix the left and right subtrees of root

   root->left = removeOutsideRange(root->left, min, max);

   root->right = removeOutsideRange(root->right, min, max);

   // Now fix the root. There are 2 possible cases for toot

   // 1.a) Root's key is smaller than min value (root is not in range)

   if (root->key < min)

   {

       node *rChild = root->right;

       delete root;

       return rChild;

   }

   // 1.b) Root's key is greater than max value (root is not in range)

   if (root->key > max)

   {

       node *lChild = root->left;

       delete root;

       return lChild;

   }

   // 2. Root is in range

   return root;

}

// A utility function to create a new BST node with key as given num

node* newNode(int num)

{

    node* temp = new node;

    temp->key = num;

    temp->left = temp->right = NULL;

    return temp;

}

// A utility function to insert a given key to BST

node* insert(node* root, int key)

{

    if (root == NULL)

       return newNode(key);

    if (root->key > key)

       root->left = insert(root->left, key);

    else

       root->right = insert(root->right, key);

    return root;

}

// Utility function to traverse the binary tree after conversion

void inorderTraversal(node* root)

{

    if (root)

    {

        inorderTraversal( root->left );

        cout << root->key << " ";

        inorderTraversal( root->right );

    }

}

// Driver program to test above functions

int main()

{

    node* root = NULL;

    root = insert(root, 3);

    root = insert(root, 7);

    root = insert(root, 4);

    root = insert(root, 8);

    root = insert(root, 15);

    root = insert(root, 13);

    root = insert(root, 6);

    cout << "Inorder traversal of the given tree is: ";

    inorderTraversal(root);

    root = removeOutsideRange(root, 0, 13);

    cout << " Inorder traversal of the modified tree is: ";

    inorderTraversal(root);

    return 0;

}

Output:

Inorder traversal of the given tree is: 3 7 4 8 15 13 6

Inorder traversal of the modified tree is: 3 4 6 7 8 13

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.