Codiwan.com

The blog for Design Patterns, Linux, HA and Myself!

In this article we’ll be solving the problem: Sum of Left Leaves. Just like the problem, Same Tree or Equal Tree and Leaf Similar Trees, this problem also requires a slight modification in a simple Tree Traversal approach.

```		```

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.

```
```

The solution to this problem requires a slight modification in the Tree Traversal approach. We’ll be using the Pre Order Tree Traversal approach to solve this problem.

In order to check if a node is a left child, or a right child, we’ll pass a boolean flag from the parent to the child node. If the child is a left child then the flag will be true otherwise false. This way we’ll be able to identify if a node is a left child, or a right child.

Next, to check if a node is a leaf node we’ll put a null check on the children of the node.

Here’s the code for this problem. It can be found here on GitHub as well.

``````var sum int
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}
sum = 0
if root.Left != nil {
preOrder(root.Left, true)
}
if root.Right != nil {
preOrder(root.Right, false)
}
return sum
}

func preOrder(node *TreeNode, left bool) {
if node.Left == nil && node.Right == nil && left {
sum += node.Val
}
if node.Left != nil {
preOrder(node.Left, true)
}
if node.Right != nil {
preOrder(node.Right, false)
}
}
``````

Here the function `sumOfLeftLeaves` calls `preOrder` to traverse the tree. The `preOrder` function is checking if a node is a left node, and if is a left child, after that it adds the value of the node to the sum.