Top view of binary tree

Dhanaraj S
Apr 11, 2022

--

Check out the problem description here.

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)

--

--

Dhanaraj S
Dhanaraj S

Written by Dhanaraj S

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

No responses yet