Binary Tree Traversal in C++

C++ Program for Binary Tree Traversal in data structure

#include<iostream>
#include<stack>
#include<queue>

using namespace std;
 
class Node{
public:
    Node* lchild;
    int data;
    Node* rchild;
    Node() {};
    Node(int data);
};
 
Node::Node(int data) {
    lchild = nullptr;
    this->data = data;
    rchild = nullptr;
}
 
class Tree{
private:
    Node* root;
public:
    Tree();
    void CreateTree();
    void Preorder(Node* p);
    void Preorder() { Preorder(root); }  // Passing Private Parameter in Constructor
    void Inorder(Node* p);
    void Inorder() { Inorder(root); }
    void Postorder(Node* p);
    void Postorder() { Postorder(root); }
    void Levelorder(Node* p);
    void Levelorder() { Levelorder(root); }
    int Height(Node* p);
    int Height() { return Height(root); }
    void iterativePreorder(Node* p);
    void iterativePreorder() { iterativePreorder(root); }
    void iterativeInorder(Node* p);
    void iterativeInorder() { iterativeInorder(root); }
    void iterativePostorder(Node* p);
    void iterativePostorder() { iterativePostorder(root); }
    Node* generateFromTraversal(int inorder[], int preorder[], int inStart, int inEnd);
};
 
Tree::Tree() {
    root = nullptr;
}

void Tree::CreateTree() {
    Node* p;
    Node* t;
    int x;
    queue<Node*> q;
 
    root = new Node;
    cout << "Enter root data: " << flush;
    cin >> x;
    root->data = x;
    root->lchild = nullptr;
    root->rchild = nullptr;  
    q.emplace(root);
 
    while (! q.empty()){
        p = q.front();
        q.pop();
 
        cout << "Enter left child data of " << p->data << ": " << flush;
        cin >> x;
        if (x != -1){
            t = new Node;
            t->data = x;
            t->lchild = nullptr;
            t->rchild = nullptr;
            p->lchild = t;
            q.emplace(t);
        }
 
        cout << "Enter right child data of " << p->data << ": " << flush;
        cin >> x;
        if (x != -1){
            t = new Node;
            t->data = x;
            t->lchild = nullptr;
            t->rchild = nullptr;
            p->rchild = t;
            q.emplace(t);
        }
    }
}
 

Binary tree traversal iterative

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

void Tree::iterativeInorder(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 << ", " << flush;
            p = p->rchild;
        }
    }
    cout << endl;
}

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

Recursive Binary tree traversal

void Tree::Preorder(Node *p) {
    if (p){
        cout << p->data << ", " << flush;
        Preorder(p->lchild);
        Preorder(p->rchild);
    }
}
 
void Tree::Inorder(Node *p) {
    if (p){
        Inorder(p->lchild);
        cout << p->data << ", " << flush;
        Inorder(p->rchild);
    }
}
 
void Tree::Postorder(Node *p) {
    if (p){
        Postorder(p->lchild);
        Postorder(p->rchild);
        cout << p->data << ", " << flush;
    }
}

Level order traversal

void Tree::Levelorder(Node *p) {
    queue<Node*> q;
    cout << p->data << ", " << flush;
    q.push(p);
 
    while (! q.empty()){
        p = q.front();
        q.pop();
 
        if (p->lchild){
            cout << p->lchild->data << ", " << flush;
            q.push(p->lchild);
        }
 
        if (p->rchild){
            cout << p->rchild->data << ", " << flush;
            q.push(p->rchild);
        }
    }
}
 

Reverse Level Order Traversal

vector<int> reverseLevelOrder(Node *p)
{
    
    vector<int> ans;
      if(!p)
      return ans;
      queue<Node *> q;
      q.push(p);
      Node * temp;
      while(!q.empty())
      {
          temp=q.front();
          q.pop();
          if(temp->right)
          q.push(temp->right);
          if(temp->left)
          q.push(temp->left);
          
          ans.push_back(temp->data);
      }
      reverse(ans.begin(),ans.end());
      return ans;
}

Binary Tree Zigzag Level Order Traversal

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> ans;
        vector<int> v;
        int count=0;
        TreeNode* p;
        queue<TreeNode * > q;
        q.push(root);
        int size=0;
        while(!q.empty())
        {
            v.clear();
            count++;
            size=q.size();
           
            for(int i=0;i<size;i++)
            {
                 p=q.front();
                 q.pop();
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
                v.push_back(p->val);
                
            }
            if(count%2==0)
            {
                    reverse(v.begin(),v.end());
            }
            ans.push_back(v);
        }
        return ans;
    }

Vertical Traversal of Binary Tree

vector<int> verticalOrder(Node *root)
    {
        queue<pair<Node *,int>> q;
        vector<int> v;
        vector<vector<int>> ans;
        map<int,vector<int>> mp;
        q.push(make_pair(root,0));
        while(!q.empty())
        {
            pair<Node *,int> p=q.front();
            q.pop();
            Node  * temp=p.first;
            int pos=p.second;
            if(temp->left)
                q.push(make_pair(temp->left,pos-1));
            if(temp->right)
                q.push(make_pair(temp->right,pos+1));
            mp[pos].push_back(temp->data);
            
        }
        for(auto &pr:mp)
        {
            for(int i=0;i<pr.second.size();i++)
            {
                v.push_back(pr.second[i]);
            }
            
        }
        return v;
    }