Sum of Left Leaves

Sum of Left Leaves

What is this problem about?

The "Sum of Left Leaves" problem asks you to find the sum of all leaf nodes that are left children in a binary tree. A "leaf" is a node with no children. A "left leaf" is a leaf node that is the left child of its parent. For example, in a tree where the root 3 has a left child 9 and a right child 20 (and 20 has children 15 and 7), the only left leaf is 9 and 15.

Why is this asked in interviews?

This "Easy" level problem is a staple at Amazon, Meta, and Bloomberg. It tests a candidate's ability to perform tree traversals (DFS or BFS) and their ability to pass state through recursive calls. Specifically, it tests whether a candidate can distinguish between a general left child and a left leaf.

Algorithmic pattern used

The pattern used is Tree Traversal (Depth-First Search or Breadth-First Search).

• DFS Approach: Recursively visit each node. When visiting a node, check if its left child is a leaf. A child is a leaf if child.left == null && child.right == null. If it is, add its value to the sum.
• BFS Approach: Use a queue to visit nodes level by level. For each node, check its left child. If that child is a leaf, add it to the running total.

Example explanation

Consider this tree: 3 /
9 20 /
15 7

• Start at 3. Check left child (9). 9 is a leaf (no children). Add 9.
• Check right child (20). 20 is not a leaf. Move to its children.
• At 20, check left child (15). 15 is a leaf. Add 15.
• At 20, check right child (7). 7 is a leaf, but it's a right leaf, so ignore it. Total Sum = 9 + 15 = 24.

Common mistakes candidates make

1. Including Non-Leaf Left Children: Adding the value of a left child even if it has children of its own.
2. Including Right Leaves: Mistakenly adding all leaf nodes regardless of whether they are left or right children.
3. Null Pointer Exceptions: Not checking if a child exists before trying to access its own children (e.g., root.left.left).

Interview preparation tip

Always clarify the definition of a "leaf." For tree problems, practice both recursive and iterative solutions. Recursive solutions are often cleaner for trees, but iterative solutions using a stack or queue demonstrate a deeper understanding of memory management.