Path to given node

Check out the problem description here.

Solution

class Solution:
def solve(self, A, B):
ds=[]
self.rec(A,B,ds)
return ds
def rec(self,root,B,ds):
if root ==None :
return False
ds.append(root.val)
if root.val == B:
return True
if self.rec(root.left,B,ds) or self.rec(root.right,B,ds):
return True
ds.pop(-1)
return False

Time :O(N)

Space :O(h) height of the tree

--

--

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)

--

--

Top view of binary tree

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)

--

--

Dhanarajappu

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