Sum of Left Leaves

Updated on 04 July, 2025
Sum of Left Leaves header image

Problem Statement

The task involves identifying a specific type of node, known as a left leaf, in a binary tree and computing their cumulative value. For clarity, a leaf in the context of binary trees is a node that does not have any children. More specifically, a left leaf is classified as any leaf that acts as the left child of its parent node. Given the root node of a binary tree, the objective is to return the sum of values of all these left leaves.

Examples

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

Approach and Intuition

To solve the problem of finding and summing all left leaves in a binary tree, you can apply either iterative or recursive strategies. Given the nature of tree traversals, a recursive approach can be inherently more intuitive. Here’s a basic plan using recursion:

  1. Start from the root and initiate a sum that keeps track of the values of left leaves.
  2. For each node, determine if it has a left child which is a leaf:
    • Check if the left child exists and if it does not have further children (i.e., both its left and right children are null).
    • If it is a left leaf, add its value to the sum.
  3. Recursively repeat the process for both left and right children of the current node.
  4. Terminate the recursion when a null node is encountered, which is a base case returning zero (as there's nothing to sum).

In this approach, each node of the tree is visited exactly once, thereby ensuring an O(n) complexity where n is the number of nodes in the tree. This is efficient given the constraints. This method keeps the overhead low and works well within provided constraints (node values between -1000 and 1000, and up to 1000 nodes).

Examples provided demonstrate both cases with multiple left leaves and a simple tree with no leaves, helping illustrate how the sum dynamically accumulates based on tree structure.

Solutions

  • Java
java
class Solution {
  public int calculateLeftLeavesSum(TreeNode root) {
    int sum = 0;
    TreeNode current = root;
    while (current != null) {
      if (current.left == null) {
        current = current.right;
      } else {
        TreeNode temp = current.left;
        if (temp.left == null && temp.right == null) {
          sum += temp.val;
        }
        while (temp.right != null && temp.right != current) {
          temp = temp.right;
        }
        if (temp.right == null) {
          temp.right = current;
          current = current.left;
        } else {
          temp.right = null;
          current = current.right;
        }
      }
    }
    return sum;
  }
}

The provided Java program defines a method calculateLeftLeavesSum designed to calculate the sum of the left leaves in a binary tree. This method uses an iterative traversal approach to navigate through the tree, leveraging a modified version of the Morris traversal technique which avoids the need for additional memory for stack or recursion.

Here's how the method works:

  1. Initialize a variable sum to zero to keep track of the cumulative sum of the leaf values.
  2. Start traversing the binary tree from the root node using a current pointer.
  3. Utilize a while loop to process nodes until there are no more nodes to process (current becomes null).
  4. Within the loop, check if the left child of the current node does not exist:
    • If true, move to the right child of the current node.
    • Otherwise, process the left subtree of the node.
  5. If the left child of the current node itself has no children, it is a left leaf:
    • Add its value to sum.
  6. Check if the rightmost child of the left subtree has been visited by looking at a temporary temp that navigates through the right children.
    • If temp.right is null, it means this subtree hasn’t been fully explored:
      • Make temp.right point to the current node for a return path and then move current to its left child.
    • If temp.right is not null, it means returning after the left subtree is fully explored:
      • Set temp.right back to null to restore the original tree structure and move current to its right child.

The method continuously updates the sum whenever a left leaf is found, finally returning the sum after the tree is fully traversed. This solution is efficient as it avoids using extra space for recursion or a stack, making it suitable for large trees.

  • C
c
int calculateLeftLeafSum(struct TreeNode* root) {
    int total = 0;
    while (root) {
        if (!root->left) {
            root = root->right;
        } else {
            struct TreeNode* precursor = root->left;
            if (precursor->left == NULL && precursor->right == NULL) total += precursor->val;
            while (precursor->right && precursor->right != root) precursor = precursor->right;
            if (!precursor->right) {
                precursor->right = root;
                root = root->left;
            } else {
                precursor->right = NULL;
                root = root->right;
            }
        }
    }
    return total;
}

The provided C code implements a function to calculate the sum of left leaves in a binary tree. This function, calculateLeftLeafSum, uses a non-recursive approach to traverse the tree, ensuring efficient memory usage.

  • The function is initialized with a total set to 0 to hold the sum of left leaf values.
  • It checks each node starting from the root using a while loop.
  • If the current node does not have a left child, traversal moves to the right child.
  • If a left child exists, the program checks if it is a leaf (i.e., it does not have its own children). If it is a leaf, its value is added to total.
  • For non-leaf left children, a "predecessor" finder loop ensures each node's left subtree is fully explored before moving back to the right subtree. This involves temporarily modifying the tree structure by making right children of discovered nodes point back to the current node. This technique avoids the use of a parent pointer or a stack.
  • After a subtree is processed, the temporary pointers are reverted to restore the tree structure, and the next right child is processed.

This code effectively finds and sums the values of all left leaves in the binary tree without using additional space for recursion or a stack, which is a common challenge in similar tree problems.

Comments

No comments yet.