Sum of Left Leaves

Problem

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Recursive solution

public class Solution {
    public int sumOfLeftLeaves (TreeNode root) {
        if (root == null) return 0;
        int sum = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) sum += root.left.val;
        return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

BFS solution with Queue

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int sum = 0;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node.left != null && node.left.left == null && node.left.right == null) sum += node.left.val;
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        return sum;
    }
}

Analysis

Typical tree traversal problem
Since we need to calculate the sum of all left leaves, we need to know when we reach the left leaf
The key code is if (node.left != null && node.left.left == null && node.left.right == null)
We increment the sum if above statement return true and then keep our traversal of the tree
The ideas in both solutions are similar, expect the implementation

Complexity

• Time: O(n), where n is the number of nodes
• Space: O(n), in worst case the queue will have all nodes of tree (when the tree is skewed)