Skip to main content

404. Sum of Left Leaves

easy

Return the sum of all left leaves in a binary tree. A clean tree-recursion warm-up that hinges on threading a boolean — 'am I a left child?' — through the recursive call.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, return the sum of all left leaves. A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Constraints

  • The number of nodes in the tree is in the range [1, 1000].
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
24

Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2

Input
root = [1]
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse with the node and a boolean isLeft.

Hint 2

If node is a leaf and isLeft, return node.val. Else return 0 if leaf.

Hint 3

Else: return helper(node.left, true) + helper(node.right, false).

Hint 4

Alternative — at each parent, check if its left child is a leaf and add it directly.

Solution approach

Reveal approach

Two clean recursions. Approach 1 (carry an isLeft flag): helper(node, isLeft): if node is null, return 0. If node is a leaf and isLeft, return node.val. Otherwise return helper(node.left, true) + helper(node.right, false). Initial call: helper(root, false). Approach 2 (parent-checks-child): sumLeftLeaves(node): if node is null, return 0. result = 0. If node.left and node.left is a leaf, result += node.left.val. Otherwise result += sumLeftLeaves(node.left). result += sumLeftLeaves(node.right). Both are O(n) time, O(h) recursion space. The first is slightly cleaner.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • recursion
  • dfs
  • tree-traversal

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg

More Recursion practice problems

See all Recursion problems →