Answers for "binary tree traversal"

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;
}

bst traversal

//The following code contains all the DFS traversal 
//I have first created a Binary search tree 
//Then performed DFS search :- 1.Inorder;2.Preorder;3.Postorder
#include <iostream>

using namespace std;
struct node
{
    int data;
    node* left;
    node*right;
};
node* getnode(int value)
{
    node* temp=new node;
    temp->data=value;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}
node* insert_bst(node* roots,int value)
{
    if(roots==NULL)
    {
       return getnode(value);
    }
    if(roots->data>value)
    {
        roots->left=insert_bst(roots->left,value);
    }
    else if(roots->data<value)
    {
        roots->right=insert_bst(roots->right,value);
    }
    return roots;
}
void Inorder(node* roots)
{
    if(roots==NULL)
    {
       return;
    }
    else
    {
        Inorder(roots->left);
        cout<<roots->data<<" ";
        Inorder(roots->right);
    }
}
void post_order(node* roots)
{
    if(roots==NULL)
    {
        return;
    }
    else
    {
        post_order(roots->left);
        post_order(roots->right);
        cout<<roots->data<<" ";
    }
}
void preorder(node* root)
{
    if(root==NULL)
        return;
    cout<<root->data<<" ";
    preorder(root->left);
    preorder(root->right);
}
int main()
{
    node* root=new node;
    root=NULL;
    int number_of_nodes;
    cin>>number_of_nodes;
    int value;
    for(int i=0;i<number_of_nodes;i++)
    {
        cin>>value;
        root=insert_bst(root,value);
    }
    cout<<"Inorder Travesral:"<<endl;
    Inorder(root);
    cout<<endl;
    cout<<"Postorder traversal:"<<endl;
    post_order(root);
    cout<<endl;
    cout<<"preorder traversal:"<<endl;
    preorder(root);
    cout<<endl;
    return 0;
}

inorder traversal

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        return dfs(root, list);
    }
    private List<Integer> dfs(TreeNode root, List<Integer> list)
    {
        if(root == null)
            return list;
        list = dfs(root.left, list);
        list.add(root.val);
        return dfs(root.right,list);
    }
}