How do you approach Sum of Left Leaves?

A node alone can't tell you if it's a left leaf - you need to know how you reached it.

What is the time complexity of Sum of Left Leaves?

Time complexity: O(n) - each node visited once. Space complexity: O(h) for the traversal stack.

What are common mistakes on Sum of Left Leaves?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Sum of Left Leaves

EasyData Structures

Description

Given the root of a binary tree, return the sum of all left leaves. A left leaf is a leaf node that is the left child of its parent.

Note: The tree is given as a level-order array where the node at index i has its left child at index 2*i + 1 and its right child at index 2*i + 2, with null for missing nodes (trailing positions may be omitted).

For example, [3, 9, 20, null, null, 15, 7] represents:

The left leaves are 9 and 15, so the answer is 24.

Example 1

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

Output: 24

Explanation: There are two left leaves, 9 and 15.

Example 2

Input: root = [1]

Output: 0

Explanation: The root is not a left leaf.

Example 3

Input: root = []

Output: 0

Constraints

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

Sum of Left Leaves: approach, complexity and pitfalls

An easy trees problem, graded against 7 test cases (4 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

If you are stuck

Show the 3-step hint ladder

A node alone can't tell you if it's a *left* leaf - you need to know how you reached it.
Traverse from each parent: check whether its left child exists and is a leaf (no children of its own).
With the array representation, the children of index i are at 2i+1 and 2i+2; a node is a leaf when both child positions are missing or null.

The optimal approach

Show the approach: DFS Checking Left Children

Traverse the tree (DFS or BFS). For each node, look at its left child: if that child exists and has no children of its own, it is a left leaf - add its value. Right subtrees are still traversed, because they may contain left leaves deeper down.

With the level-order array representation, node `i`'s children live at `2i+1` and `2i+2`, so leaf-checking is two index lookups.

Time: O(n) - each node visited once
Space: O(h) for the traversal stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

← Back to problems

Sum of Left Leaves

EasyData Structures

Description

Given the root of a binary tree, return the sum of all left leaves. A left leaf is a leaf node that is the left child of its parent.

For example, [3, 9, 20, null, null, 15, 7] represents:

The left leaves are 9 and 15, so the answer is 24.

Example 1

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

Output: 24

Explanation: There are two left leaves, 9 and 15.

Example 2

Input: root = [1]

Output: 0

Explanation: The root is not a left leaf.

Example 3

Input: root = []

Output: 0

Constraints

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

Sum of Left Leaves: approach, complexity and pitfalls

An easy trees problem, graded against 7 test cases (4 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

If you are stuck

Show the 3-step hint ladder

A node alone can't tell you if it's a *left* leaf - you need to know how you reached it.
Traverse from each parent: check whether its left child exists and is a leaf (no children of its own).
With the array representation, the children of index i are at 2i+1 and 2i+2; a node is a leaf when both child positions are missing or null.

The optimal approach

Show the approach: DFS Checking Left Children

With the level-order array representation, node `i`'s children live at `2i+1` and `2i+2`, so leaf-checking is two index lookups.

Time: O(n) - each node visited once
Space: O(h) for the traversal stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.