Implement a stack using a BST

Question

I want to implement a stack (push and pop operations) using a BST.

During post order traversal in a BST, root is placed at the top in the stack, while traversing iteratively. So, does that mean I have to insert and delete elements from the root or something else?

Answer 1

  int num=1;
  struct node
 {
     int flag;
     int val;
     node *left,*right,*parent;
  };

 node* tree::InorderTraversalusingInBuiltstack()
 {
      stack<node *> p;
      node *current=root;

     while(!p.empty()|| current!=NULL)
     {
          while(current!=NULL)
          {
               p.push(current);
               current=current->left;
          }
          current=p.top();
          if(current->flag==num)
          {
              return current;
           }
           p.pop();
           current=current->right;
      }
  }


  void tree::StackUsingBST()
  {
      node *q;

      while(root!=NULL)
       {
              num--;

              q=InorderTraversalusingInBuiltqueue();


              node *a=q->parent;
              if(a!=NULL)
              {
                  if(a->left==q)
                       a->left=NULL;
                  else
                       a->right=NULL;

                  q->parent=NULL;
                  delete q;

                  disp();
                  cout<<endl;
               }

               else
               {

                  delete q;
                  root=NULL;
                }



      } 
   }

Here my approach is that i modified my data structure a bit, by using a flag variable as a global variable;

suppose first i insert 8 then its corresponding flag value is 1 then insert 12 its flag value=2 then insert 3 its flag value=3

now inorder to use BST as a stack I have to delete the element which has been inserted last , and according to my algo having highest flag value.

Also note that the last element inserted will not have any child so its deletion is quite easy.

In order to find the highest flag value available with the nodes, I did a inordertraversal using stack which is better than its recursive traversal.

After finding that node corresponding to highest flag value ,I delete that node. this process is repeated until root=NULL.