I was going through some coding problems related to Views(Top view, Left View, Bottom View, and Right View). So, I decided to share my knowledge with you guys. Keep reading :)
Firstly, let me introduce each view with a brief description.
- The top view of a binary tree is the set of nodes visible when the tree is viewed from the top.
- The left view of a binary tree is the set of nodes visible when the tree is viewed from left.
- The right view of a binary tree is the set of nodes visible when the tree is viewed from right.
- The bottom view of a binary tree is the set of nodes visible when the tree is viewed from bottom.
Top View
Steps to find Top View:-
- Create a queue and a map.
- Push the root node inside the queue.
- In class Tree, initialize int hd = 0 as its member.
- Now map the value with of root with its hd(Horizontal Distance).
- Now make a while loop which will run until the queue becomes empty.
- Now pop out the element and check if hd count in map == 0, then map it with its horizontal distance i.e., hd.
- Check whether it has left child, if yes then firstly map the root-<left value with hd-1, and then push it in the queue.
- Similarly, check for the right child, and map it with hd+1, and push inside the queue.
What we are doing here is, we have defined horizontal distance of root node = 0, as we move leftwards, its horizontal distance decreases by 1 and for rightwards, its horizontal distance increases by 1. Then in Step 6, we are checking if the element is already present at that horizontal distance or not, if it is present, then we don't map the root value with hd. As we want only the top view nodes.
Refer to this image to understand horizontal distance in a better way.
I Will Continue this topic for next type of views, as I like to keep my blog short, so stay connected and please follow me for new updates :)
Top comments (0)