Head add

Binary Tree Traversal in C++

Binary tree traversal: It is the process of visiting (or printing) all the nodes of the binary tree. There are three ways for tree traversal that are Pre-order, In-order, and Post-order.
    Pre-order In-order Post-order
    Process the root R. Traverse the left subtree of R in preorder. Traverse the left sub tree of R in postorder.
    Traverse the left subtree of R in preorder. Process the root R. Traverse the right subtree of R inorder.
    Traverse the right subtree of R in preorder Traverse the right subtree of R inorder. Process the root R.

    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

    Preorder Traversal:
    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;
    }
    
    Inorder Traversal:
    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;
    }
    
    Postorder Traversal:
    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

    In this program, we will learn print level order traversal of a tree.
    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;
        }
    
    Siddharth Jha
    • Hackerrank 5* • Full Stack Developer • Masters in SEO
    Newest Older

    Related Posts

    Post a Comment