# Bottom view of a tree

Apr 12, 2022

--

Check out the problem description here

https://www.codingninjas.com/codestudio/problems/893110?topList=striver-sde-sheet-problems&utm_source=striver&utm_medium=website&leftPanelTab=1

Solution

Traverse level order, and pushing the nodes to queue with the node and its x coordinate(position of imaginary vertical line ) .While popping the node from queue keep updating the imaginary vertical line with latest value popped from the queue and which belong to the corresponding imaginary vertical line .Finally return the dictionary.

`def bottomView(root):    res=[]    q=[]    map_str=dict()    temp=[]    if root:        q.append([root,0])    while(q):        size = len(q)        for i in range(size):            front = q.pop(0)            x=front[1]            map_str[x]=front[0].data            if front[0].left:                q.append([front[0].left,x-1])            if front[0].right:                q.append([front[0].right,x+1])    for i in sorted(map_str):        temp.append(map_str[i])    return temp`

Time : O(N)

Space: O(N)

--

--

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.