Answers for "vertical traversal of 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
        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);

    map<int, vector<int>> m;

        Obj *ob = q.front();

        if(m.find(ob->dis) != m.end())
            vector<int> v;
            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

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) 
		//get the vector list at 'hd' 
		Vector<Integer> get = m.get(hd); 
		// Store current node in map 'm' 
		if(get == null) 
			get = new Vector<>(); 
		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; 
		// Traverse the map and print nodes at every horigontal 
		// distance (hd) 
		for (Entry<Integer, Vector<Integer>> entry : m.entrySet()) 
	// 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"); 
Posted by: Guest on May-04-2020

Code answers related to "vertical traversal of binary tree"

Code answers related to "Java"

Java Answers by Framework

Browse Popular Code Answers by Language