#include <iostream>
#include <queue>

using namespace std;
class Node
{
public:
    int data;
    Node* lchild;
    Node* rchild;
};
class Tree
{
public:
    Tree(){root = nullptr;}
    void CreateTree();
    void Preorder()
    {
        Preorder(root);
    }
    void Preorder(Node* p);
    void Inorder(){ Inorder(root); }
    void Inorder(Node* p);
    void Postorder(){ Postorder(root); }
    void Postorder(Node* p);
    void Levelorder(){ Levelorder(root);}
    void Levelorder(Node* p);
    int Height(){ return Height(root);}
    int Height(Node* p);


private:
    int l = 0;
    int r = 0;
    Node* root;
};
int Tree::Height(Node* p)
{
    if(p==nullptr)
        return 0;

    l = Height(p->lchild);
    r = Height(p->rchild);

    if(l>r)
    {
        return l+1;
    }
    else
    {
        return r+1;
    }

}
void Tree::Levelorder(Node* p)
{
    queue<Node*> q;
    cout << root->data << " , ";
    q.push(root);
    Node* t = p;

    while(!q.empty())
    {
        t = q.front();
        q.pop();

        if(t->lchild)
        {
            cout<< t->lchild->data<<",";
            q.push(t->lchild);
        }
        if(t->rchild)
        {
            cout<<t->rchild->data<<",";
            q.push(t->rchild);
        }

    }
}
void Tree::Postorder(Node* p)
{
    if(p)
    {
        Inorder(p->lchild);
        Inorder(p->rchild);
        cout<<p->data;
    }
}
void Tree::Inorder(Node* p)
{
    if(p)
    {
        Inorder(p->lchild);
        cout<<p->data;
        Inorder(p->rchild);
    }
}
void Tree::Preorder(Node* p)
{
    if(p)
    {
        cout<<p->data<<" ";
        Preorder(p->lchild);
        Preorder(p->rchild);
    }
}
void Tree::CreateTree()
{
    Node* p;
    Node* t;
    int x;
    queue<Node*> q;

    cout<<"Enter Root value: ";
    cin>>x;
    cout<<endl;

    root = new Node;
    root->data =x;
    root->lchild = root->rchild = nullptr;
    q.push(root);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        cout<<"enter left child of " <<p->data << ": ";
        cin>>x;
        cout<<endl;
        if(x!=-1)
        {
            t = new Node;
            t->data = x;
            t->lchild = t->rchild = nullptr;
            p->lchild = t;
            q.push(t);
        }
        cout<<"enter Right child of " <<p->data << ": ";
        cin>>x;
        cout<<endl;
        if(x!=-1)
        {
            t = new Node;
            t->data = x;
            t->lchild = t->rchild = nullptr;
            p->rchild = t;
            q.push(t);
        }
    }
}
int main()
{
    Tree t;
    t.CreateTree();
    cout<<"Preorder";
    t.Preorder();
    cout<<endl;
    cout<<"Inorder ";
    t.Inorder();
    cout<<endl;
    cout<<"Postorder: ";
    cout<<endl;
    t.Postorder();
    cout<<"Levelorder: ";
    cout<<endl;
    t.Levelorder();
    cout<<"Height: ";
    cout<<endl;
    t.Height();

    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
class Node
{
public:
    int data;
    Node* lchild;
    Node* rchild;
};
class Tree
{
public:
    Tree(){root = nullptr;}
    void CreateTree();
    void Preorder()
    {
        Preorder(root);
    }
    void Preorder(Node* p);
    void Inorder(){ Inorder(root); }
    void Inorder(Node* p);
    void Postorder(){ Postorder(root); }
    void Postorder(Node* p);
    void Levelorder(){ Levelorder(root);}
    void Levelorder(Node* p);
    int Height(){ return Height(root);}
    int Height(Node* p);
    void iterativePreorder(){iterativePreorder(root);}
    void iterativePreorder(Node* p);
    void iterativeIneorder(){iterativeIneorder(root);}
    void iterativeIneorder(Node* p);
    void iterativePostorder(){iterativePostorder(root);}
    void iterativePostorder(Node* p);
private:
    int l = 0;
    int r = 0;
    Node* root;
};
void Tree::iterativePostorder(Node* p)
{
    stack<Node*> stk;
    while(p!=nullptr || !stk.empty())
    {
        if(p!=nullptr)
        {
            stk.push(p);
            p = p->lchild;
        }
        else
        {
            p = stk.top();
            stk.pop();
            cout<<p->data <<", ";
            iterativePostorder(p->rchild);
            }
        }
    cout <<endl;
}
void Tree::iterativeIneorder(Node* p)
{
    stack<Node*> stk;
    while(p!=nullptr || !stk.empty())
    {
        if(p!=nullptr)
        {
            stk.push(p);
            p = p->lchild;
        }
        else
        {
            p = stk.top();
            stk.pop();
            cout << p->data << " , ";
            p = p->rchild;
        }
    }
    cout <<endl;

}
void Tree::iterativePreorder(Node* p)
{
    stack<Node*> stk;
    while(p!=nullptr || !stk.empty())
    {
        if(p!=nullptr)
        {
            cout << p->data << " , ";
            stk.push(p);
            p = p->lchild;
        }
        else
        {
            p = stk.top();
            stk.pop();
            p = p->rchild;
        }
    }
    cout <<endl;

}
int Tree::Height(Node* p)
{
    if(p==nullptr)
        return 0;

    l = Height(p->lchild);
    r = Height(p->rchild);

    if(l>r)
    {
        return l+1;
    }
    else
    {
        return r+1;
    }

}
void Tree::Levelorder(Node* p)
{
    queue<Node*> q;
    cout << root->data << " , ";
    q.push(root);
    Node* t = p;

    while(!q.empty())
    {
        t = q.front();
        q.pop();

        if(t->lchild)
        {
            cout<< t->lchild->data<<",";
            q.push(t->lchild);
        }
        if(t->rchild)
        {
            cout<<t->rchild->data<<",";
            q.push(t->rchild);
        }

    }
}
void Tree::Postorder(Node* p)
{
    if(p)
    {
        Inorder(p->lchild);
        Inorder(p->rchild);
        cout<<p->data;
    }
}
void Tree::Inorder(Node* p)
{
    if(p)
    {
        Inorder(p->lchild);
        cout<<p->data;
        Inorder(p->rchild);
    }
}
void Tree::Preorder(Node* p)
{
    if(p)
    {
        cout<<p->data<<" ";
        Preorder(p->lchild);
        Preorder(p->rchild);
    }
}
void Tree::CreateTree()
{
    Node* p;
    Node* t;
    int x;
    queue<Node*> q;

    cout<<"Enter Root value: ";
    cin>>x;
    cout<<endl;

    root = new Node;
    root->data =x;
    root->lchild = root->rchild = nullptr;
    q.push(root);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        cout<<"enter left child of " <<p->data << ": ";
        cin>>x;
        cout<<endl;
        if(x!=-1)
        {
            t = new Node;
            t->data = x;
            t->lchild = t->rchild = nullptr;
            p->lchild = t;
            q.push(t);
        }
        cout<<"enter Right child of " <<p->data << ": ";
        cin>>x;
        cout<<endl;
        if(x!=-1)
        {
            t = new Node;
            t->data = x;
            t->lchild = t->rchild = nullptr;
            p->rchild = t;
            q.push(t);
        }
    }
}
int main()
{
    Tree t;
    t.CreateTree();
    cout<<"Preorder";
    t.Preorder();
    cout<<endl;
    cout<<"Inorder ";
    t.Inorder();
    cout<<endl;
    cout<<"Postorder: ";
    cout<<endl;
    t.Postorder();
    cout<<"Levelorder: ";
    cout<<endl;
    t.Levelorder();
    cout<<"Height: ";
    cout<<endl;
    t.Height();

    cout<<"Iterative Preorder: ";
    cout<<endl;
    t.iterativePreorder();

    cout<<"Iterative inorder: ";
    cout<<endl;
    t.iterativeIneorder();

    cout<<"Iterative Postorder: ";
    cout<<endl;
    t.iterativePostorder();

    return 0;
}