LeetCode 404. Sum of Left Leaves

Question: https://leetcode.com/problems/sum-of-left-leaves/

Unlike the other tree questions, the iterative solution is more intuitive and easier to come up with than the recursive one. The iterative solution is a simple application of Breath First Search (BFS). We just need to insert some code to check if the left node is a leaf when we insert that node back into the queue. The solution runs in 24ms and uses 12.3MB (slower than the recursive solution below, but use less space).

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = 0
        q = deque()
        if root:
            q.append(root)
            visited = {}
            while q:
                v = q.popleft()
                if v not in visited:
                    if v.left:
                        if not v.left.left and not v.left.right:
                            ans += v.left.val
                        q.append(v.left)
                    if v.right:
                        q.append(v.right)
                    visited[v] = True
        return ans

The recursive solution is harder to write because we need information that is above the current level. The information we need is if the node under observation is a left leaf. This information cannot be gained without using an auxiliary recursive helper. A recursive helper is simply a wrapper that allows one to append additional information to the function. If we just recursively call the original function sumOfLeftLeaves(root), there is no way we can add any additional information, since the function arguments are fixed. Therefore, we have defined an inner function with the isLeft argument to tell the function of whether the node that we passed is a left child or not. Given this freedom, we now know if the node passed is a left node or not, if it's a left node, then we apply the same logic as it is in the iterative BFS solution, we check if this node is a leaf, if so, we simply add the value to the answer.

# 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
        """
         def recursive_helper(root, isLeft):
             ans = 0
             if root:
                 if isLeft and (not root.left and not root.right):
                     ans += root.val
                 else:
                     ans += recursive_helper(root.left, True)
                     ans += recursive_helper(root.right, False)
             return ans
            
         return recursive_helper(root, False)
            

Related Question:

• Maximum Binary Tree: https://monkeyinvestment.blogspot.com/2020/03/leetcode-654-maximum-binary-tree.html
• Binary Tree Paths: https://monkeyinvestment.blogspot.com/2020/03/leetcode-257-binary-tree-paths.html