/* 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<>();
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);
}
}
Posted by: Guest
on May-04-2020
Code answers related to "aan efficent level order traversal of a binary tree reqiures use of"
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems
resetting your password contact us
Check Your Email and Click on the link sent to your email