Top view of a binary tree

In this chapter we shall learn how to print top view of a binary tree.

Problem Statement:

You are given a root node of the tree print the top view of the tree.

For example:

Consider the below tree:

So the top view will be

d b a c g

Let’s see how do we arrive at this solution.

We can solve this problem by applying level order traversal and vertical order traversal.

Now let’s see how these 2 traversal will help us to get the top view of the tree.

The level order traversal of the tree will give the result as below:

a b c d e f g

For the vertical traversal we need to calculate the Horizontal Distance.

For the horizontal distance, of the tree is as below:

Now we shall list according to ascending order of the horizontal distance [HD], it will be as below:

Now if we observe the table with HD value of 0, we have written it as “a, e, f” because all the 3 nodes are in the same HD value.

But why we dint write as “e, a, f” or “f, a, e”? Because, we have applied level order traversal and from that we know that “a” comes first, then “e” then f.

From the table it is clear that we need to take the first nodes at each HD value to arrive at the result.