# Answers for "vertical traversal of binary tree"

2

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;
}``````
Posted by: Guest on June-09-2020
0

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<>();
}
else

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);
}
}``````
Posted by: Guest on May-04-2020