Sum of Left Leaves

EASY

Description

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

Checkout 3 different approaches to solve Sum of Left Leaves. Click on different approaches to view the approach and algorithm in detail.

Recursive Depth-First Search

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.

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 Analysis

Time Complexity: O(N), where N is the number of nodes in the tree. We must visit every node to check its children.Space Complexity: 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).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Sum of Left Leaves. Click on different languages to view the code.

/** * 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 Solution

Watch the video walkthrough for Sum of Left Leaves

Algorithms:

Depth-First SearchBreadth-First Search

Data Structures:

TreeBinary Tree

Companies:

Grammarly |