binary tree inorder traversal code example

Example 1: vertical traversal of binary tree

/* This is just a function of vertical traversal of binary tree. You need to 
   write required code. Thank you. */

// Class to store node and it's distance from parent.
class Obj
{
    public:
        Node *root;
        int dis;

        Obj(Node *node, int dist)
        {
            root = node;
            dis = dist;
        }
};

// Main logic of vertical traversal.
void verticalTraversal(Node *root)
{
    queue<Obj*> q;
    Obj *ob = new Obj(root, 0);
    q.push(ob);

    map<int, vector<int>> m;

    while(!q.empty())
    {
        Obj *ob = q.front();
        q.pop();

        if(m.find(ob->dis) != m.end())
        {            
            m[ob->dis].push_back(ob->root->data);
        }   
        else
        {   
            vector<int> v;
            v.push_back(ob->root->data);
            m[ob->dis] = v;
        }

        if(ob->root->left != NULL)
            q.push(new Obj(ob->root->left, ob->dis-1));
        if(ob->root->right != NULL)
            q.push(new Obj(ob->root->right, ob->dis+1));
    }

    for(auto it=m.begin(); it!=m.end(); it++)
    {
        vector<int> v1 = (*it).second;
        for(int j = 0; j<v1.size(); j++)
            cout << v1[j] << "\t";
    }

    cout << endl;
}

Example 2: preorder traversal

#include <iostream>
using namespace std;

class node{
public:
    int data;
    node* left;
    node* right;

    node(int d){
        data = d;
        left = NULL;
        right = NULL;
    }
};

node* buildTree(){
    int d;
    cin>>d;

    if(d==-1){
        return NULL;	//to attach a NULL pointer[in case of no child] enter -1
    }
    node * root = new node(d);
    root->left = buildTree();
    root->right = buildTree();
    return root;
}



//REQUIRED FUNCTION: Inorder Traversal


void printIn(node*root){
    if(root==NULL){
        return;
    }
    //Otherwise Left Root Right
    printIn(root->left);
    cout<<root->data<<" ";
    printIn(root->right);
}


int main(){ 
    node* root = buildTree();
    printIn(root);

	return 0;
}

//SAMPLE INPUT TO RUN THE CODE ON ANY ONLINE IDE:
//8 10 1 -1 -1 6 9 -1 -1 7 -1 -1 3 -1 14 13 -1 -1 -1

Tags:

Misc Example