Question

IN C++

 

Create a binary search tree of stacks where each node contains a key and a stack. In this binary search tree, when adding a new element to the tree it is inserted based off of its key value; if that key value already exist then the element is pushed into the stack at that location, if the key value does not exist a node element is added to the tree to reflect that key, and a empty stack is created where you will push the element to be inserted. When removing elements from the tree, you will pop elements at that specific key until the stack is empty; when the stack becomes empty that node will be removed from the tree and one of its decedents need to take its place in the tree.

Answer 1

// C++ function to search a given key in a given BST

struct node* search(struct node* root, int key)

{

    // Base Cases: root is null or key is present at root

    if (root == NULL || root->key == key)

       return root;

    

    // Key is greater than root's key

    if (root->key < key)

       return search(root->right, key);

    // Key is smaller than root's key

    return search(root->left, key);

}

// C++ program to demonstrate insertion

// in a BST recursively.

#include
using namespace std;

class BST
{
   int data;
   BST *left, *right;

   public:
  
   // Default constructor.
   BST();
  
   // Parameterized constructor.
   BST(int);
  
   // Insert function.
   BST* Insert(BST *, int);
  
   // Inorder traversal.
   void Inorder(BST *);
};

// Default Constructor definition.
BST :: BST() : data(0), left(NULL), right(NULL){}

// Parameterized Constructor definition.
BST :: BST(int value)
{
   data = value;
   left = right = NULL;
}

// Insert function definition.
BST* BST :: Insert(BST *root, int value)
{
   if(!root)
   {
       // Insert the first node, if root is NULL.
       return new BST(value);
   }

   // Insert data.
   if(value > root->data)
   {
       // Insert right node data, if the 'value'
       // to be inserted is greater than 'root' node data.
      
       // Process right nodes.
       root->right = Insert(root->right, value);
   }
   else
   {
       // Insert left node data, if the 'value'
       // to be inserted is greater than 'root' node data.
      
       // Process left nodes.
       root->left = Insert(root->left, value);
   }
  
   // Return 'root' node, after insertion.
   return root;
}

// Inorder traversal function.
// This gives data in sorted order.
void BST :: Inorder(BST *root)
{
   if(!root)
   {
       return;
   }
   Inorder(root->left);
   cout << root->data << endl;
   Inorder(root->right);
}

// Driver code
int main()
{
   BST b, *root = NULL;
   root = b.Insert(root, 50);
   b.Insert(root, 30);
   b.Insert(root, 20);
   b.Insert(root, 40);
   b.Insert(root, 70);
   b.Insert(root, 60);
   b.Insert(root, 80);

   b.Inorder(root);
   return 0;
}