#include<vector>
using namespace std;
//template based class for BST
template<class X>
class Tree
{
    private:
        //structure of node of BST
        struct Node
        {
            X data;
            Node *left, *right;
        };
        //array to store the value of nodes
        vector<int>arr;
        int i;
    public:
        //method to create a new node
        Node* newNode(X data)
        {
            Node *temp=new Node;
            temp->data=data;
            temp->right=temp->left=NULL;
            return temp;
        }
    private:
        //Method for inorder traversal
        //to store the node value in array in sorted order
        void inorder(Node *root)
        {
            if(root==NULL)
                return;
            //recursion on left subtree
            inorder(root->left);
            //copying data of node in the array
            arr.push_back(root->data);
            //recursion on right subtree
            inorder(root->right);
        }
        //Method for conversion of BST to min heap
        void bstToHeap(Node *root)
        {
            if(root==NULL)
                return;
            root->data=arr[++i];
            bstToHeap(root->left);
            bstToHeap(root->right);
        }
    public:
        // root node of BST
        Node *root;
        //Constructor
        Tree()
        {
            root=NULL;
            i=-1;
        }

        void minHeap ()
        {
            //inorder traversal to populate array
            inorder(root);
            //BST to min heap conversion
            bstToHeap(root);
        }
        //method for preorder traversal
        void preorder(Node *root)
        {
            if(root==NULL)
                return;
            //printing root data
            cout<<root->data<<" ";
            //recursion on left subtree
            preorder(root->left);
            //recursion on right subtree
            preorder(root->right);
        }
};
//Driver program
int main()
{
    //Formation of BSt tree
    Tree <int>t;
    t.root=t.newNode(4);
    t.root->left=t.newNode(2);
    t.root->right=t.newNode(6);
    t.root->left->left=t.newNode(1);
    t.root->left->right=t.newNode(3);
    t.root->right->left=t.newNode(5);
    t.root->right->right=t.newNode(7);
    t.minHeap ();
    cout<<"Preorder Traversal:"<<endl;
    t.preorder(t.root);
    return 0;
}