In this post, we will discuss a method to print the Top view of a binary tree. This is one the most common easy level interview questions. Also, you might get to see interview questions which can be solved with slight variations to this code.
Top View of a tree is defined as the nodes that would be visible to us if we viewed the tree from the top. To do this we have to maintain horizontal distance of all the nodes from the root node and print the first node for each horizontal distance. This problem can be solved easily with simple traversal and use of data structures. Have a look at the below image to get some idea.
In the above image, the horizontal distance of the root is set to 0 and for all the node to the right we increase the horizontal distance by 1 and for all the node to the right, we decrease the horizontal distance by 1. Thus, the problem reduces to printing the first node with a horizontal distance that is not been traversed before.
Let's have a look at the code.
Top View of a tree is defined as the nodes that would be visible to us if we viewed the tree from the top. To do this we have to maintain horizontal distance of all the nodes from the root node and print the first node for each horizontal distance. This problem can be solved easily with simple traversal and use of data structures. Have a look at the below image to get some idea.
Top view of a binary tree |
In the above image, the horizontal distance of the root is set to 0 and for all the node to the right we increase the horizontal distance by 1 and for all the node to the right, we decrease the horizontal distance by 1. Thus, the problem reduces to printing the first node with a horizontal distance that is not been traversed before.
Let's have a look at the code.
C++ Program
Sample input and output to check the program
You might also be interested in
Bottom View of a Binary Tree
Left View of a Binary Tree
Right View of a Binary Tree
Comments
Post a Comment