#include<iostream>
/* Class represent the linked list */
template<class X>
class LinkList{
    private:

        /*structure represents the node of linked list*/
        struct LNode
        {
            int data;
            LNode *LNext;
        };

    public:

        LNode *start; //head pointer of linked list
        /* Constructor */
        LinkList(){
            start=NULL;
        }

        /*Function to insert the node in linked list */
        void push(X data)
        {
            LNode *temp=new LNode;
            temp->data=data;
            temp->LNext=NULL;
            if(start==NULL)
                start=temp;
            else
            {
                LNode *t=new LNode;
                t=start;
                while(t->LNext!=NULL)
                    t=t->LNext;
                t->LNext=temp;
            }
        }

        /* Method to print the linked list */
        void PrintList()
        {
            if(start==NULL)
                std::cout<<"List is Empty "<<std::endl;
            else
            {
                LNode *temp=new LNode;
                temp=start;
                std::cout<<"Elements of list are: ";
                while(temp!=NULL)
                {
                    std::cout<<temp->data<<" ";
                    temp=temp->LNext;
                }
            }
        }
};

/* Class represents Binary search tree */
template<class X>
class Tree
{
    private:
        /* Structure represents the tree node */
        struct TNode
        {
            X data;
            TNode *left;
            TNode *right;
        };

    public:

        TNode *root; //root of binary search tree
        /* Constructor */
        Tree()
        {
            root=NULL;
        }

    private:

        //Method to create a new node
        TNode* CreateNode(X data)
        {
            TNode *temp=new TNode;
            temp->data=data;
            temp->left=temp->right=NULL;
            return temp;
        }

        // Method to insert the node
        void InsertNode(X data)
        {
            TNode *temp=CreateNode(data);
            TNode *par=NULL;
            //Base case means tree does not exist
            if(root==NULL)
                root=temp;
            else //Tree exist
            {
                par = root;
                while (par != NULL )
                {
                    if(par->data>data)
                    {
                        if(par->left==NULL)
                        {
                            par->left=temp;
                            break;
                        }
                        par = par -> left;
                    }
                    if(par->data<data)
                    {
                        if(par->right==NULL)
                        {
                             par->right=temp;
                             break;
                         }
                        par = par -> right;
                    }
                }
            }
        }

    public:

        //Method to construct Binary Search Tree
        void ConstructBst(LinkList<int>::LNode *NodeList)
        {
            while(NodeList!=NULL)
            {
                InsertNode(NodeList->data);
                NodeList=NodeList->LNext;
            }
        }

        // Method to print postorder traversal of constructed binary search tree
        void PrintPostorder(TNode *r)
        {
            if(r)
            {
                PrintPostorder(r->left);
                PrintPostorder(r->right);
                std::cout<<r->data<<" ";
            }
        }
};
//Driver function
int main()
{
    LinkList<int>list;//LinkList object represent a linked list
    list.push(5);
    list.push(7);
    list.push(9);
    list.push(15);
    list.push(25);
    list.PrintList();
    Tree <int>BST;
    BST.ConstructBst(list.start);
    std::cout<<std::endl<<"Postorder Traversal of constructed BST is: ";
    BST.PrintPostorder (BST.root);
    return 0;
}