Scale Engineer

Sum of Left Leaves

Easy
#0391Time: O(N), where N is the number of nodes in the tree. We must visit every node to check its children.Space: O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).1 company
Algorithms
Depth-First SearchBreadth-First Search
Data structures
TreeBinary Tree
Companies
Grammarly

Prompt

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.

 

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

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses recursion to perform a depth-first traversal of the tree. The core idea is to define a function that, for any given node, calculates the sum of left leaves in the subtree rooted at that node. To identify a left leaf, we look ahead from a parent node. When at a node curr, we check its left child, curr.left. If curr.left exists and is a leaf (meaning it has no children), we've found a left leaf and add its value to our sum. We then recursively apply the same logic to the left and right subtrees to find all other left leaves.

Algorithm

  • Base Case: If the current node root is null, return 0.
  • Initialize a local variable sum to 0.
  • Check if the left child of the current node is a leaf. A node n is a leaf if n.left == null and n.right == null.
  • If root.left is a leaf, add its value to sum.
  • Recursively call the function on the left subtree (root.left) and add the returned value to sum.
  • Recursively call the function on the right subtree (root.right) and add the returned value to sum.
  • Return the total sum.

Walkthrough

This approach uses recursion to perform a depth-first traversal of the tree. The core idea is to define a function that, for any given node, calculates the sum of left leaves in the subtree rooted at that node.

To identify a left leaf, we don't check the current node itself. Instead, we look ahead from a parent node. When we are at a node curr, we check its left child, curr.left. If curr.left exists and is a leaf (meaning it has no children), we've found a left leaf and add its value to our sum. We then recursively apply the same logic to the left and right subtrees to find all other left leaves.

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public int sumOfLeftLeaves(TreeNode root) {        if (root == null) {            return 0;        }         int sum = 0;        // Check if the current node's left child is a leaf.        if (root.left != null && root.left.left == null && root.left.right == null) {            sum += root.left.val;        }         // Recursively find the sum in the left and right subtrees.        sum += sumOfLeftLeaves(root.left);        sum += sumOfLeftLeaves(root.right);         return sum;    }}

Complexity

Time

O(N), where N is the number of nodes in the tree. We must visit every node to check its children.

Space

O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).

Trade-offs

Pros

  • Code is concise and closely follows the recursive definition of a tree.

  • Easy to understand and implement.

Cons

  • Can lead to a StackOverflowError for very deep trees.

  • Function call overhead can be slightly less performant than an iterative solution.

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int sumOfLeftLeaves ( TreeNode root ) { if ( root == null ) { return 0 ; } int res = 0 ; if ( root . left != null && root . left . left == null && root . left . right == null ) { res += root . left . val ; } res += sumOfLeftLeaves ( root . left ); res += sumOfLeftLeaves ( root . right ); return res ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem