# Children Sum Property

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)

--

--

# 257. Binary Tree Paths

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

--

--

# 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

--

--

# 101 Symmetric tree

Check the problem description here

Solution

Recursive solution

Recursively check if the mirror nodes are same.

`class Solution:    def isSymmetric(self, root: Optional[TreeNode]) -> bool:        if root:            return self.helper(root.left,root.right)        else:            return False    def helper(self,n1,n2):        if n1==None or n2==None :            return n1==n2        if n1.val != n2.val:            return False        return (self.helper(n1.left,n2.right) and   self.helper(n1.right,n2.left))`

Time :O(N)

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