Sum of Left Leaves — Solution in Python, Java & C++
Sum of Left Leaves solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sum of Left Leaves is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Adobe and Bloomberg interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Adobe, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the sum of all its left leaves.
A leaf is a node with no children; a left leaf is a leaf that is the left child of its parent. The root itself is never a left leaf.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: The left leaves are 9 and 15; 7 is a right leaf and does not count.
Example 2
Input: root = [1]
Output: 0
Explanation: The root has no parent, so it is not a left leaf.
Example 3
Input: root = [1,2,3,4,5]
Output: 4
Explanation: 2 is a left child but not a leaf; its left child 4 is the only left leaf.
Constraints
The number of nodes in the tree is in the range [1, 1000]-1000 <= Node.val <= 1000
Hints for Sum of Left Leaves
Hint 1
Whether a node is a left leaf depends on its parent, so decide it while standing on the parent.
Hint 2
At a node, look at its left child: if that child exists and has no children, add its value.
Hint 3
Otherwise keep walking into both subtrees — left leaves can sit under right children too.
How to solve Sum of Left Leaves
A node is a left leaf when its parent reached it through a left pointer and it has no children. Checking from the parent's side makes that test local: at every node, inspect node.left.
Approach
- If
rootis null, return 0. - If
root.leftexists and is a leaf, countroot.left.val; otherwise recurse intoroot.left. - Recurse into
root.rightand add its result.
Why it works
Every left leaf has exactly one parent, and the walk visits every non-leaf node, so each left leaf is counted exactly once — at its parent. Right leaves are never added because only .left children are tested.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth
Pitfalls
- A single-node tree answers 0: the root is not a left leaf.
- A left child that has children is not a leaf — descend into it instead.
- Values can be negative; the sum can be negative too.
Reference solution
Python
from typing import Optional
def sumOfLeftLeaves(root: Optional[TreeNode]) -> int:
if root is None:
return 0
total = 0
left = root.left
if left is not None and left.left is None and left.right is None:
total += left.val
else:
total += sumOfLeftLeaves(left)
return total + sumOfLeftLeaves(root.right)Java
public static int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int total = 0;
TreeNode left = root.left;
if (left != null && left.left == null && left.right == null) total += left.val;
else total += sumOfLeftLeaves(left);
return total + sumOfLeftLeaves(root.right);
}C++
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
int total = 0;
TreeNode* left = root->left;
if (left && !left->left && !left->right) total += left->val;
else total += sumOfLeftLeaves(left);
return total + sumOfLeftLeaves(root->right);
}JavaScript
var sumOfLeftLeaves = function(root) {
if (root === null) return 0;
var total = 0, left = root.left;
if (left !== null && left.left === null && left.right === null) total += left.val;
else total += sumOfLeftLeaves(left);
return total + sumOfLeftLeaves(root.right);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)