Top view of binary tree

Check out the problem description here.

Top View Of Binary Tree for coding interview round

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 store the first node value for each imaginary vertical line in to a dictionary .Finally return the dictionary.

def getTopView(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]
            if x not in map_str:
                map_str[x]=front[0].val
            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)