```
class Solution(object):
def sumOfLeftLeaves(self, root):
def dfs(root, left):
if not root: return
if left and not root.left and not root.right:
cache[0] += root.val
dfs(root.left, True)
dfs(root.right, False)
cache = [0]
dfs(root, False)
return cache[0]
```

Complexity is `O(n)`

time and `O(n)`

space. This is because we use DFS so it takes stack space proportional to height of tree (which is `n`

in the worst case).