Recursive DFS

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]

Node	isLeft	Is Leaf?	Contribution
3	false	No	recurse
9	true	Yes	+9
20	false	No	recurse
15	true	Yes	+15
7	false	Yes	+0

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).