Sum of left children — Preorder traversal

Easy

Sum of Left Leaves

Easy : https://leetcode.com/problems/sum-of-left-leaves/

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

Iterative Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        # 3:39 pm
        # a leaf is the one with no children
        # is must be linked from a parent? not in the case of a root.
        
        # we can do a inorder traversal, skip all processing of the right and top nodes.
        # we all all the leaves except the last one.
        self.res = []
        
        def inorder(root, child):
            if root:
                if root.left: 
                    inorder(root.left, "l")
                if root.right:
                    inorder(root.right, "r")
                    
                if not root.left and not root.right and child == "l" :
                    self.res += [root.val]
                    
        inorder(root, "")
        return sum(self.res)

Recursive Code:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        # 3:39 pm- 3:56 pm
        # a leaf is the one with no children
        # is must be linked from a parent? not in the case of a root.
        
        # we can do a inorder traversal, skip all processing of the right and top nodes.
        # we all all the leaves except the last one.
        
        
        def preorder(root, is_left):
            if not root:
                return 0
            
            if not root.left and not root.right:
                return root.val if is_left else 0
            
            return preorder(root.left, True) + preorder(root.right, False)
                    
        return preorder(root, False)

Complexity Analysis

Let N be the number of nodes.

Time complexity : O(N)

• The code within the recursive function is all O(1). The function is called exactly once for each of the N nodes. Therefore, the total time complexity of the algorithm is O(N).

Space complexity : O(N)

• In the worst case, the tree consists of nodes that form a single deep strand. In this case, the runtime-stack will have NN calls to preorder(...) on it at the same time, giving a worst-case space complexity of O(N).