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.```

## Solution

### DFS Approach – Recursive

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int SumOfLeftLeaves(TreeNode root) {
return DFS(root,false);
}
public int DFS(TreeNode root,bool isLeft){
if(root == null){
return 0;
}

if(root.left == null && root.right == null && isLeft){
return root.val;
}

return DFS(root.left,true) + DFS(root.right,false);
}
}
```

## Iterative Approach – Using Stack

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int SumOfLeftLeaves(TreeNode root) {
int sum = 0;

if(root == null)
return sum;

Stack<TreeNode> s = new Stack<TreeNode>();
s.Push(root);

while(s.Count > 0){

TreeNode node = s.Pop();

if(node.left != null){

if(node.left.left == null && node.left.right == null){

sum += node.left.val;

}
else
s.Push(node.left);
}

if(node.right != null){

if(node.right.left != null || node.right.right!=null){

s.Push(node.right);
}
}
}
return sum;

}
}
```

In both the approaches, Time Complexity and Space Complexity is O(n)