In this tutorial, we shall solve how to print bottom view of a binary tree.
Problem statement:
You are given a binary tree; you need to print the bottom view of a binary tree.
Consider the tree:
So the solution would be h d b f i g j
This problem can be solved in 4 steps.
Step 1: Calculate the horizontal distance for every node.
Step 2: Create a hash table, list down all the horizontal distance in ascending order.
Step 3: For each horizontal distance, list down all the nodes with similar height. If 2 nodes have the same value, they should be entered in level order traversal order.
Step 4: Finally select the last node from all the horizontal distance.
//add vertical order traversal code here
So how to calculate horizontal distance at every node?
For root node horizontal distance will be 0.
For left Child:
horizontal_distance = parent_horizontal_distance - 1
For Right Child:
horizontal_distance = parent_horizontal_distance + 1
So let’s calculate horizontal distance for all the nodes.
a = root node = 0
b = parent node value - 1 = 0 - 1 = -1
c = parent node value + 1 = 0 + 1 = 1
d = - 1 - 1 = -2
e = - 1 + 1 = 0
f = 1 - 1 = 0
g = 1 + 1 = 2
h = -2 - 1 = -3
i = 2 - 1 = 1
j = 2 + 1 = 3
It can be showed as below:
Now we shall create a hash map in ascending order as below
Now let’s fill the data:
For -1 there is only 1 value, hence insert h
For -2 there is only 1 value, hence insert d
For -1 there is only 1 value, hence insert b
For 0 there is only 3 value, hence insert according to level order traversal. Hence insert a, e, f.
For 1 there is only 2 value, hence insert c, i in order
For 2 there is only 1 value, hence insert g
For 3 there is only 1 value, hence insert j
So the table will look like below:
Now select the last elements, you will get the bottom view:
i.e h d b f i g j