Sum of Left Leaves

The challenge is distinguishing a left leaf from a right leaf. We solve this by passing a boolean flag isLeft to the recursive helper that indicates whether the current node was reached as a left child. When we find a leaf node with isLeft == true, we add its value to the sum.

Algorithm:

• Call the helper with the root, marking it as isLeft = false.
• If the node is null, return 0.
• If the node is a leaf and isLeft is true, return the node's value.
• Otherwise, recurse: pass true for the left child, false for the right child.

public int sumOfLeftLeaves(TreeNode root) {
    return dfs(root, false);
}

private int dfs(TreeNode node, boolean isLeft) {
    if (node == null) return 0;

    // leaf node that was reached as a left child
    if (node.left == null && node.right == null) {
        return isLeft ? node.val : 0;
    }

    return dfs(node.left,  true)   // left child → isLeft = true
         + dfs(node.right, false);  // right child → isLeft = false
}

Trace through Example 1: root = [3,9,20,null,null,15,7]

Total = 9 + 15 = 24.

• Time: O(n). Every node is visited exactly once.
• Space: O(h). Recursion stack depth equals the tree height h (O(log n) for balanced trees, O(n) worst case for skewed trees).