Sum of Left Leaves

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

Question

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

Example:

Input：
{3,9,20,#,#,15,7}
Output：24

Explanation：There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
    3
   / \
  9  20
    /  \
   15   7


Input:
{1,#,2,#,3}
Output:
0

Explanatinon:
1
  \
    2
      \
       3

Analyzation

Recursion

This problem needs a helper that check whether a node is a left node.

Steps:

• If the node is left, isLeft = True, if the node is right, isLeft = Right
• If the node has no children and is a left node, return the val
• If the node has both left and right nodes, sum them up because the result is for the summation of all the left nodes from both left and right subtrees
• If the node has only left or right, just return them correspondingly.

The Code

class Solution:
    """
    @param root: t
    @return: the sum of all left leaves
    """
    def sumOfLeftLeaves(self, root):
        # Write your code here
        if root is None or (root.left is None and root.right is None):
            return 0
        
        return self.dfs(root, True)
        
    def dfs(self, node, isLeft):
        if node is None:
            return None
            
        # get the left node and left node is the left tree's node so isLeft == True
        # and the right node is not left tree's node so isLeft == False
        left = self.dfs(node.left, True)
        right = self.dfs(node.right, False)
        
        # if the node is a leaf node and it is at the left side, just get the value
        if left is None and right is None and isLeft:
            return node.val
        
        # if the node has both left and right nodes, sum them up
        if left and right:
            return left + right
        
        # if only has left node, return itself and check back later, same as right node
        if left:
            return left
        
        if right:
            return right
            
        return 0

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).