Bottom view of a tree

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)