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

--

--

Dhanarajappu

Dhanarajappu

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