Answers for "vertical traverse binary tree"

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

vertical traversal of binary tree

// Java program for printing vertical order of a given binary tree 
import java.util.TreeMap; 
import java.util.Vector; 
import java.util.Map.Entry; 

public class VerticalOrderBtree 
{ 
	// Tree node 
	static class Node 
	{ 
		int key; 
		Node left; 
		Node right; 
		
		// Constructor 
		Node(int data) 
		{ 
			key = data; 
			left = null; 
			right = null; 
		} 
	} 
	
	// Utility function to store vertical order in map 'm' 
	// 'hd' is horizontal distance of current node from root. 
	// 'hd' is initially passed as 0 
	static void getVerticalOrder(Node root, int hd, 
								TreeMap<Integer,Vector<Integer>> m) 
	{ 
		// Base case 
		if(root == null) 
			return; 
		
		//get the vector list at 'hd' 
		Vector<Integer> get = m.get(hd); 
		
		// Store current node in map 'm' 
		if(get == null) 
		{ 
			get = new Vector<>(); 
			get.add(root.key); 
		} 
		else
			get.add(root.key); 
		
		m.put(hd, get); 
		
		// Store nodes in left subtree 
		getVerticalOrder(root.left, hd-1, m); 
		
		// Store nodes in right subtree 
		getVerticalOrder(root.right, hd+1, m); 
	} 
	
	// The main function to print vertical order of a binary tree 
	// with the given root 
	static void printVerticalOrder(Node root) 
	{ 
		// Create a map and store vertical order in map using 
		// function getVerticalOrder() 
		TreeMap<Integer,Vector<Integer>> m = new TreeMap<>(); 
		int hd =0; 
		getVerticalOrder(root,hd,m); 
		
		// Traverse the map and print nodes at every horigontal 
		// distance (hd) 
		for (Entry<Integer, Vector<Integer>> entry : m.entrySet()) 
		{ 
			System.out.println(entry.getValue()); 
		} 
	} 
	
	// Driver program to test above functions 
	public static void main(String[] args) { 

		// TO DO Auto-generated method stub 
		Node root = new Node(1); 
		root.left = new Node(2); 
		root.right = new Node(3); 
		root.left.left = new Node(4); 
		root.left.right = new Node(5); 
		root.right.left = new Node(6); 
		root.right.right = new Node(7); 
		root.right.left.right = new Node(8); 
		root.right.right.right = new Node(9); 
		System.out.println("Vertical Order traversal is"); 
		printVerticalOrder(root); 
	} 
}