Dhanarajappu

Check the problem description here.

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

Solution:

As we recursively go to left and right , we replace child data , with root data, if the root is less than the root , so that while we come back the child of a node is always higher than the root. So that we can increment the root value(make it left +right data).

def changeTree(root): 
if root ==None:
return
left=0
right=0
if root.left!=None:
if root.left.data<root.data:
root.left.data=root.data
changeTree(root.left)
left=root.left.data
if root.right!=None:
if root.right.data<root.data:
root.right.data=root.data
changeTree(root.right)
right=root.right.data
if not (root.left==None and root.right==None):
root.data=left+right

Time:O(N)

Space:O(h)

--

--

Check out the problem description here.


class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res=[]
ds=[]

self.rec(root,res,ds)
for i in range(len(res)):
res[i] = "->".join(res[i])
return(res)

def rec(self,root,res,ds):
if root ==None:
return
ds.append(str(root.val))

if root.left ==None and root.right==None:
res.append(ds.copy())
ds.pop(-1)
return
self.rec(root.left,res,ds)
self.rec(root.right,res,ds)
ds.pop(-1)

The above code in a much more neat code is given below


class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res=[]
if root:
self.rec(root,"",res)
return res

def rec(self,root,path,res):
path+=str(root.val)

if root.right==None and root.left ==None:
res.append(path)
return
if root.left:
self.rec(root.left,path+"->",res)
if root.right:
self.rec(root.right,path+"->",res)

Both solution takes the same time and complexity

TIME :O(n) n= number of nodes

SPACE :O(h) h = height of the 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)

--

--

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

Dhanarajappu

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