Sum of Left Leaves - Video Solutions

Problem Overview: You are given the root of a binary tree and need to compute the sum of all left leaves. A left leaf is a node that is both a left child of its parent and has no children of its own. The task is essentially a traversal problem: visit each node and check whether its left child qualifies as a leaf.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

This approach performs a standard recursive traversal of the binary tree. At each node, check whether the left child exists and whether that left child is a leaf (both left and right pointers are null). If so, add its value to the running sum. Otherwise, continue the recursion on both left and right subtrees. The key insight is that you don't need to process every leaf—only those reached through a left edge. Each node is visited once, giving O(n) time complexity where n is the number of nodes. The recursion stack grows up to the height of the tree, which results in O(h) auxiliary space.

This solution is concise and mirrors the natural structure of the tree. Most engineers prefer this version when solving problems involving recursive tree traversal because the logic stays close to the definition of the structure itself.

Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))

The iterative version replaces recursion with an explicit stack to simulate depth-first search. Push the root node onto a stack and repeatedly pop nodes for processing. For each node, check whether its left child exists and whether it is a leaf. If it is, add its value to the total. Otherwise push the left child to the stack so its subtree can be explored. The right child is also pushed when present so the traversal eventually covers the entire tree.

This method still visits every node exactly once, resulting in O(n) time complexity. The stack stores nodes along the current traversal path, so the space usage remains O(h), where h is the height of the tree. Iterative DFS is useful when recursion depth might be large or when you want more explicit control over traversal order in a tree structure.

Recommended for interviews: Recursive DFS is the solution most interviewers expect. It clearly demonstrates your understanding of tree traversal and keeps the implementation short and readable. Mentioning the iterative stack-based DFS shows deeper understanding and awareness of recursion limits. Both approaches achieve the optimal O(n) time complexity since every node must be inspected to determine whether it forms a left leaf.