# 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 7There are two left leaves in the binary tree, with values9and15respectively. Return24.

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 N
*N*calls to`preorder(...)`

on it at the same time, giving a worst-case space complexity of O(N).