Vertical Order Traversal In Binary Tree

Vertical order traversal is a method of traversing the elements of a binary tree – from top to bottom and left to right.

In vertical order traversal first we need to find the horizontal distance of each node.

When we are finding the horizontal distance (hd) we need to follow certain rules:

  1. For root node hd = 0.
  2. For left child hd = hd-1;
  3. for right child hd = hd+1

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \ 
       2      3
      / \   /   \
     4   5  6   7
               /  \ 
              8   9 
               
              
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

Code:

package tree;

import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;
import java.util.Vector;

public class VetricalOrderTraversal {
	
	static void getVertical(Node node, int hd, TreeMap<Integer, Vector<Integer>> map ) {
		
		
		if(node == null)
			return;
		
		if(map.get(hd) == null) {
			Vector<Integer> list = new Vector<>();
			
			list.add(node.data);
			map.put(hd, list);
		} else {
			Vector<Integer> list = map.get(hd);
			
			
			
		
			list.add(node.data);
			map.put(hd, list);
		}
		
		getVertical(node.left, hd-1, map);
		getVertical(node.right, hd+1, map);
		
	}
	static void printVertical(Node node) {
		if(node == null)
			return;
		
		int hd = 0;
		
		TreeMap<Integer, Vector<Integer>> map = new TreeMap<>();
		getVertical(node, hd, map);
		
		for(Map.Entry<Integer, Vector<Integer>> ans : map.entrySet()) {
			System.out.print(ans.getValue() + " ");
			
		}
	}

	public static void main(String[] args) {
		Node root= new Node(10); 
        root.left= new Node(4); 
      root.right= new Node(19); 
      root.left.left= new Node(8); 
     root.left.right= new Node(2); 
     root.left.right.left= new Node(15); 
     root.right.left= new Node(12); 
     root.right.right= new Node(5); 
     root.right.left.right= new Node(-3); 
         
       System.out.println("Vertical Order traversal of binary tree is "); 
      printVertical(root);
	}

}

Output:

Vertical Order traversal of binary tree is 
[8] [4, 15] [10, 2, 12] [19, -3] [5] 

Time Complexity of hashing based solution can be considered as O(n) under the assumption that we have good hashing function that allows insertion and retrieval operations in O(1) time. In the above java implementation map of Collections is used.

 Therefore time complexity of the above implementation is O(nLogn).

Hope you all get the concept of vertical order traversal using recursive approach.

To learn recursion and tree traversal in details .

In the next blog we will see other tree implementation using both methods i.e iterative and recursive in java.

So till then Bye Bye…!

Happy Coding..!

Thank You…!



Categories: JAVA

Tags: , , , , , ,

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: