Sum Of Left Leaves - Leetcode Solution

Problem Statement: 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. The sum of the left leaves is 9 + 15 = 24.

Solution: To solve this problem, we can apply recursion which is the most intuitive and easy-to-understand approach.

We can define a recursive function named helper which takes three parameters:

1. node which serves as the root of the current subtree.
2. is_left which indicates whether the current node is a left child of its parent.
3. sum_val which is the sum of all left leaves found so far.

Then, at each recursive call, we check whether the current node is a left leaf (i.e., it has a null left and right child) and if it is, we add its value to sum_val.

We also recursively call the helper function on the left and right subtrees of the current node, passing the appropriate arguments for is_left and sum_val.

The base case for the recursion is when the current node is null, in which case we simply return sum_val.

Here is the code for the solution:

class Solution: def sumOfLeftLeaves(self, root: TreeNode) -> int: return self.helper(root, False, 0)

def helper(self, node, is_left, sum_val):
    if node is None:
        return sum_val
    
    if node.left is None and node.right is None and is_left:
        sum_val += node.val
    
    sum_val = self.helper(node.left, True, sum_val)
    sum_val = self.helper(node.right, False, sum_val)
    
    return sum_val

Time Complexity: O(n) where n is the number of nodes in the binary tree. Space Complexity: O(h) where h is the height of the binary tree (i.e., the maximum number of function calls on the call stack at any one time). However, in the worst case where the binary tree is completely unbalanced, the height can be O(n), making the space complexity O(n).

1