Answers for "vertical level order traversal of a tree using hash table"

C++
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 "vertical level order traversal of a tree using hash table"

Browse Popular Code Answers by Language