Sum of Left Leaves

In this page, we will solve the Sum of Left Leaves problem using Depth-First Search (DFS). We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

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

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
Explanation: There are no left leaves in the binary tree. The tree only has one node, which is the root node itself. Therefore, the sum of left leaves is 0.

Constraints

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

---

Solution for Sum of Left Leaves

Intuition and Approach

Recursive DFS Traversal:

• Traverse the tree starting from the root.
• For each node, check if it has a left child that is a leaf. If so, add the value of that leaf to the sum.
• Recursively traverse the left and right subtrees.

Base Case:

• If the current node is null, return 0.

Leaf Check:

• A node is a leaf if it has no left or right children.

• Maximum Calculation
• Simulation

Implementation

• Here's the implementation in multiple languages:

Live Editor

function sumOfLeftLeaves(root) {
  let sum = 0;

  function dfs(node) {
    if (!node) return;

    if (node.left && !node.left.left && !node.left.right) {
      sum += node.left.val;
    }

    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);
  return sum;
}

Result

Loading...

Code in Different Languages

JavaScript

Written by @manishh12

 function sumOfLeftLeaves(root) {
let sum = 0;

function dfs(node) {
 if (!node) return;

 if (node.left && !node.left.left && !node.left.right) {
   sum += node.left.val;
 }

 dfs(node.left);
 dfs(node.right);
}

dfs(root);
return sum;
}

TypeScript

Written by @manishh12

   function dfs(node: TreeNode | null): void {
 if (!node) return;

 if (node.left && !node.left.left && !node.left.right) {
   sum += node.left.val;
 }

 dfs(node.left);
 dfs(node.right);
}

dfs(root);
return sum;
}

Python

Written by @manishh12

 class Solution:
     self.sum = 0

     def dfs(node):
         if not node:
             return
         
         if node.left and not node.left.left and not node.left.right:
             self.sum += node.left.val
         
         dfs(node.left)
         dfs(node.right)
     
     dfs(root)
     return self.sum

Java

Written by @manishh12

 class Solution {
 public int sumOfLeftLeaves(TreeNode root) {
     return dfs(root);
 }

 private int dfs(TreeNode node) {
     if (node == null) {
         return 0;
     }

     int sum = 0;
     if (node.left != null && node.left.left == null && node.left.right == null) {
         sum += node.left.val;
     }

     sum += dfs(node.left);
     sum += dfs(node.right);

     return sum;
 }
}

C++

Written by @manishh12

 class Solution {
public:
 int sumOfLeftLeaves(TreeNode* root) {
     if (!root) return 0;
     int sum = 0;
     dfs(root, sum);
     return sum;
 }

 void dfs(TreeNode* node, int& sum) {
     if (!node) return;

     if (node->left && !node->left->left && !node->left->right) {
         sum += node->left->val;
     }

     dfs(node->left, sum);
     dfs(node->right, sum);
 }
};

Complexity Analysis

• Time Complexity: $O(L + R)$, where L is the length of the left array and R is the length of the right array.
• Space Complexity: $O(1)$, as we are only using a few extra variables.

tip

By using a simple maximum calculation approach or a simulation approach, we can efficiently solve the Last Moment Before All Ants Fall Out of a Plank problem. The choice of implementation language depends on the specific requirements and constraints of the problem.

References

• LeetCode Problem: Last Moment Before All Ants Fall Out of a Plank
• Solution Link: Last Moment Before All Ants Fall Out of a Plank Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta