How can I take level order input? and
How can I approach this problem?
Tree Bottom View
@Kinjal
for taking input you just have to do the same as we do during the level order traversal i.e. start from taking src node input then push it in queue. Then keep adding elements to the queue accordingly till the queue is not empty.
So now Since you want to print bottom view of tree, then start traversing the tree with the help of level order traversal but also attach another variable, horizontal distance with every node, which actually denotes the distance of the current node from root.
for eg:- horizontal distance (hd) for root =0. hd for root->left = -1 and for right = +1.
then similarly for every child it is maitained, for eg:- hd for root->left->right = -1 +1 = 0 or hd for root->left->left = -1 -1 = -2.
So the basis for horizontal distance for every horizontal distance the last node of it is the only required.
in the above image example, bottom view is 7, 5, 8, 6.
so keep store in a map as mp[hd] = node. The last one for every hd is the answer if you do the traversal level order wise.
I am sharing the code for the same, if you find difficulty in understanding then can have a look at this https://ide.codingblocks.com/s/247067
1 Like
So, why can’t we just do like,
m[temp->hd]=temp=>data;
I did this way, and get it wrong output.
Oh. I get it. So, what happens when I’m not updating the hd, so it gives only m[0] elements, because I put 0 as root->hd value at start.
@Kinjal
I hope your doubt is clear now, so please mark this doubt as resolved.
If not, then you can ask right away.
okay. Doubt marked as resolved. Thank you.
1 Like