Sum of Left Leaves Solution

Leetcode Solution: Understand Leetcode problem Sum of Left Leaves(404) Solution

12 September 2020

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.

Loading Comments... Disqus Loader

Sum of Left Leaves Solution

Leetcode Solution: Understand Leetcode problem Sum of Left Leaves(404) Solution

Related Pages: