In this tutorial we shall see how to do vertical order traversal.
Problem Statement:
You are given a root node of a tree, you need to print the nodes when they are traversed vertically.
Consider the tree given below:
The vertical order traversal can be visualized as below:
So the vertical order traversal will be:
d
b
a e f
c
g
So how can we arrive at this result?
We can arrive at the result with the help of:
1. Map
2. Horizontal Distance
3. Level Order Traversal
We shall see how all these 3 takes part in arriving at the solution.
First how to calculate horizontal distance?
We can calculate horizontal distance by below steps:
1. For root node, horizontal distance = 0.
2. For left node, horizontal distance = parent horizontal distance – 1
3. For right node, horizontal distance = parent horizontal distance + 1
Now, let’s calculate horizontal distance for all the nodes.
As “a” is root node, it’s distance is 0.
b = 0 – 1 = -1
d = -1 – 1 = -2
c = 0 + 1 = 1
g = 1 + 1 = 2
e = -1 + 1 = 0
f = 1 – 1 = 0
Finally, the horizontal distance will look like below:
Now in the hash map, sort the horizontal distance value according to ascending order. Then insert the nodes according to their Horizontal Distance [HD] value.
The hash map will look like below:
Now a question arises. Why we inserted “a, e, f” in that order?
We added it with the help of level order traversal. When we do level order traversal, we get those 3 nodes in that order.
We get our result.