Sum of Left Leaves

• LeetCode: Sum of Left Leaves

• Problem:

Find the sum of all left leaves in a given binary tree.

• Examples:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

• Analysis:

As we know, leave tree is left child and right child are null.

When we want to find the left leave, we can judge it from the parent node of the left leave.

The left leave of a parent node: 

     parent.left != null && parent.left.left == null && parent.left.right == null

• Code - Java:

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

    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left != null && root.left.left == null && root.left.right == null) {
            return root.left.val + helper(root.right);
        } else {
            return helper(root.left) + helper(root.right);
        }
    }
}

• Code - C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        return helper(root);
    }

    int helper(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
            return root->left->val + helper(root->right);
        }
        return helper(root->left) + helper(root->right);
    }
};

• Code - Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.helper(root)
    def helper(self, root):
        if root == None:
            return 0
        if root.left != None and root.left.left == None and root.left.right == None:
            return root.left.val + self.helper(root.right)
        return self.helper(root.left) + self.helper(root.right)

• Code - C:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int helper(struct TreeNode* root) {
    if (root == 0) {
        return 0;
    }
    if (root->left != 0 && root->left->left == 0 && root->left->right == 0) {
        return root->left->val + helper(root->right);
    }
    return helper(root->left) + helper(root->right);
}

int sumOfLeftLeaves(struct TreeNode* root) {
    return helper(root);
}

• Time Complexity: O(N), N is the number of nodes in the tree

• Space Complexity: O(1)