Sum of Left Leaves

Easy
1870.

Sum of Left Leaves

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Whether a node is a left leaf depends on its parent, so decide it while standing on the parent.

  2. Hint 2

    At a node, look at its left child: if that child exists and has no children, add its value.

  3. 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

  1. If root is null, return 0.
  2. If root.left exists and is a leaf, count root.left.val; otherwise recurse into root.left.
  3. Recurse into root.right and 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)