404. Sum of Left Leaves

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

The problem provides us with the root of a binary tree and asks us to calculate the sum of all left leaves in the tree. In the context of this problem, a leaf is defined as a node with no children and a left leaf is specifically a leaf that is also the left child of its parent node. Our goal is to traverse the binary tree and find all the nodes that satisfy the condition of being a left leaf, and then sum their values to return the final result.

Flowchart Walkthrough

To analyze Leetcode 404, Sum of Left Leaves, using the Flowchart, we'll walk through each step:

Is it a graph?

Yes: We are dealing with a binary tree, a specific type of graph where each node has at most two children.

Is it a tree?

Yes: Since we are considering a binary tree, which by definition is a tree.

DFS

From here, the flowchart leads to an advisable focus on Depth-First Search (DFS) since the next decision point involves whether it concerns directed acyclic graphs (DAGs) or not, which is not relevant here as we are directly using DFS for navigating and processing a tree structure.

Why DFS? Depth-First Search (DFS) allows us to traverse each branch of the tree from the root to the leaves before moving onto the next branch. This functionality is crucial for this problem, as we need to examine specific conditions for all leaves, particularly to distinguish and process left leaves.

By using DFS, we can adequately explore each path and take necessary actions when encountering left leaves, summing their values as required by the problem. DFS provides an efficient means to manage and navigate through all the nodes in the necessary depth-bound manner. Furthermore, given a tree's recursive structure, DFS' recursive nature complements the problem approach well, making it a fitting choice as dictated by the flowchart's progression.

Intuition

The solution to the problem is rooted in a classic tree traversal approach. We must navigate through all the nodes of the tree to identify which ones are left leaves. Since a leaf node is one with no children, we can determine a left leaf if the following conditions are met:

The node is the left child of its parent (root.left).
The node itself does not have any children (root.left.left is None and root.left.right is None).

The process involves a recursive function that inspects each node. We can accumulate the sum incrementally during the traversal. When we hit a None node (indicating the end of a branch), we return 0 since it doesn't contribute to the sum. If we find a left leaf, we add its value to the result. After inspecting a node for being a left leaf, we continue the traversal for both its left and right children because they may have their own left leaves further down the tree. The sum of left leaf values for the entire tree is the result of aggregating the values of all left leaves found during the traversal.

The recursive nature of binary tree traversal warrants a termination condition. In this case, we return a sum of 0 when a None node (signifying a non-existent child of a leaf node) is encountered. This is the base case for our recursive calls.

Using this intuition, the function sumOfLeftLeaves correctly sums only the left leaves of the binary tree, adhering strictly to the given definitions and constraints without unnecessary computation.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The problem is solved using a recursive approach that includes the Depth-First Search (DFS) pattern. Let's break down the implementation:

Base Case: If the current node is None, which means we have reached beyond the leaf nodes, we just return 0 as there is no contribution to the sum from a non-existent leaf.
Identifying a Left Leaf:
- When the recursive call is made for a left child node, we check: a. If the left child itself is a leaf node by confirming that both the left and right children of the left child node are None. b. If the above condition is satisfied, we've identified a left leaf, and we add its value to the res (the running total of the sum of left leaves).
Recursive Calls:
- We make a recursive call on the left child of the current node to continue searching for left leaves in the left subtree.
- The result of this call (which is the sum of left leaves found in the left subtree) is added to res.
- We do not stop after checking the left child. To ensure all left leaves are accounted for, we also make a recursive call on the right child of the current node. However, this time any leaf we find will not be a left leaf (because it comes from a right child node), so we won't add their values unless they have left leaves in their own subtrees.
Returning the Result:
- After adding values from left leaves found in both the left and right subtrees, the final res value is returned, which represents the sum of all left leaves in the binary tree.

By following this approach, all nodes in the binary tree are visited once, and left leaves are identified and summed up. The use of recursion makes the code easier to understand and succinctly handles the tree traversal and left leaf summing in one coherent process. Data structures aren't explicitly used besides the inherent recursive stack that manages the sequence of function calls.

The solution is efficient as it has a time complexity of O(n), where n is the number of nodes in the tree (since each node is visited once), and space complexity is O(h), where h is the height of the tree, which corresponds to the height of the recursive call stack.

Here is the part of the code that is critical for the understanding of the recursive approach:

if root.left and root.left.left is None and root.left.right is None:
    res += root.left.val
res += self.sumOfLeftLeaves(root.left)
res += self.sumOfLeftLeaves(root.right)

This snippet includes the check for a left leaf (the if statement), and the recursive calls to traverse the left and right subtrees (the subsequent two lines). The summing up of leaf nodes’ values happens naturally with each recursive return, allowing for an elegant and effective solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Suppose we have the following binary tree:

In this tree, we have two left leaves: 9 and 15.

We start with the root node which has a value of 3. It's not a leaf, so we proceed to check its children.
We check the left child of the root, which is 9. It has no left or right children, making it a left leaf node. We add its value to res, so res = 9.
Next, we explore the right child of the root, which is 20. It's not a leaf, so we need to traverse its children.
We check the left child of node 20, which is 15. Again, it has no left or right children, qualifying it as a left leaf. We add its value to res, so now res = 9 + 15 = 24.
We continue and check the right child of node 20, which is 7. Even though 7 is a leaf, it is not a left leaf (since it's the right child of its parent), so we do not add its value to res.
Our traversal is complete, and we have successfully identified all left leaves in the binary tree. The final sum of all left leaves is 24.

Applying the given solution to this example, the following is how the recursive function sumOfLeftLeaves processes the nodes:

The base case returns 0 for non-existent nodes, which is not visible in this example but is crucial for recursion.
The identification of a left leaf is made when we check node 9 and node 15. For node 9, root.left.left and root.left.right are both None, satisfying the left leaf conditions. The same applies to node 15.
Recursive calls allow us to explore all subtrees of the binary tree. In our example, recursive calls are made to nodes 9, 20, 15, and 7, but only 9 and 15 contribute to the sum res.
The result is aggregated throughout the recursive calls and finally returns the sum of all left leaves when all nodes have been visited.

By following these steps, our recursive function would successfully return the sum of all left leaves for any binary tree given to it.

Solution Implementation

1class TreeNode:
2    # Initialization of a Tree Node
3    def __init__(self, value):
4        self.val = value  # Assign the value to the node
5        self.left = None  # Initialize left child as None
6        self.right = None  # Initialize right child as None
7
8
9class Solution:
10    # Function to calculate the sum of all left leaves in a binary tree
11    def sumOfLeftLeaves(self, root: TreeNode) -> int:
12        # If the root is None, then return 0 as there are no leaves
13        if root is None:
14            return 0
15      
16        # Initialize result as 0
17        sum_left_leaves = 0
18      
19        # Check if the left child exists and it's a leaf node
20        if root.left and root.left.left is None and root.left.right is None:
21            sum_left_leaves += root.left.val  # Add its value to the sum
22      
23        # Recursively find the sum of left leaves in the left subtree
24        sum_left_leaves += self.sumOfLeftLeaves(root.left)
25      
26        # Recursively find the sum of left leaves in the right subtree
27        sum_left_leaves += self.sumOfLeftLeaves(root.right)
28      
29        # Return the total sum of left leaves
30        return sum_left_leaves
31

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8  
9    TreeNode(int x) {
10        val = x;
11    }
12}
13
14public class Solution {
15  
16    /**
17     * Calculates the sum of all left leaves in a binary tree.
18     *
19     * @param root the root of the binary tree
20     * @return the sum of all left leaves' values
21     */
22    public int sumOfLeftLeaves(TreeNode root) {
23        // Base case: If the current node is null, return 0 since there are no leaves.
24        if (root == null) {
25            return 0;
26        }
27
28        // Initialize sum to keep track of the left leaves sum.
29        int sum = 0;
30
31        // Check if the current node has a left child and the left child is a leaf node.
32        if (root.left != null && isLeaf(root.left)) {
33            // If it's a left leaf node, add its value to the sum.
34            sum += root.left.val;
35        }
36
37        // Recursive call to traverse the left subtree and add any left leaves found to the sum.
38        sum += sumOfLeftLeaves(root.left);
39        // Recursive call to traverse the right subtree but left leaves in this subtree are not added.
40        sum += sumOfLeftLeaves(root.right);
41
42        // Return the total sum of left leaves found.
43        return sum;
44    }
45
46    /**
47     * Helper method to check if a given node is a leaf node.
48     *
49     * @param node the node to check
50     * @return true if the node is a leaf node, false otherwise
51     */
52    private boolean isLeaf(TreeNode node) {
53        return node.left == null && node.right == null;
54    }
55}
56

1#include <iostream>
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Helper function to perform a depth-first search on the binary tree to find the sum of left leaves.
16    int depthFirstSearch(TreeNode* root, bool isLeft) {
17        // Base case: If the current node is null, return 0.
18        if (root == nullptr) {
19            return 0;
20        }
21
22        // Check if the current node is a leaf node.
23        if (root->left == nullptr && root->right == nullptr) {
24            // If it is a left child, return its value; otherwise, return 0.
25            return isLeft ? root->val : 0;
26        }
27
28        // Recursively sum the values of left leaves from the left and right subtrees.
29        int leftSum = depthFirstSearch(root->left, true);
30        int rightSum = depthFirstSearch(root->right, false);
31        return leftSum + rightSum;
32    }
33
34    // Function to calculate the sum of all left leaves in a binary tree.
35    int sumOfLeftLeaves(TreeNode* root) {
36        // Call the depth-first search starting from the root.
37        // The initial call is not a left child, so isLeft is false.
38        return depthFirstSearch(root, false);
39    }
40};
41
42int main() {
43    // Example of usage:
44    // Construct a binary tree.
45    TreeNode* root = new TreeNode(3);
46    root->left = new TreeNode(9);
47    root->right = new TreeNode(20, new TreeNode(15), new TreeNode(7));
48
49    Solution solution;
50    // Calculate the sum of all left leaves in the binary tree.
51    std::cout << "Sum of left leaves: " << solution.sumOfLeftLeaves(root) << std::endl;
52
53    // Don't forget to delete allocated memory to avoid memory leaks.
54    // This is just a quick example and does not delete the entire tree.
55    delete root->right->left;
56    delete root->right->right;
57    delete root->right;
58    delete root->left;
59    delete root;
60
61    return 0;
62}
63

1// Function to perform a depth-first search on the binary tree to find the sum of left leaves.
2// root: The current node we are visiting.
3// isLeft: A boolean value indicating whether the current node is a left child.
4const depthFirstSearch = (root: TreeNode | null, isLeft: boolean): number => {
5    // Base case: If the current node is null, return 0.
6    if (!root) {
7        return 0;
8    }
9
10    // Destructuring to get the value, left child, and right child of the current node.
11    const { val, left, right } = root;
12
13    // Check if the current node is a leaf node.
14    if (!left && !right) {
15        // If it is a left child, return its value; otherwise, return 0.
16        return isLeft ? val : 0;
17    }
18
19    // Recursively sum the values of left leaves from the left and right subtrees.
20    return depthFirstSearch(left, true) + depthFirstSearch(right, false);
21};
22
23// Function to calculate the sum of all left leaves in a binary tree.
24// root: The root of the binary tree.
25function sumOfLeftLeaves(root: TreeNode | null): number {
26    // Call the depth-first search starting from the root.
27    // The initial call is not a left child, so isLeft is false.
28    return depthFirstSearch(root, false);
29}
30

Time and Space Complexity

The provided Python code defines a function sumOfLeftLeaves that calculates the sum of all left leaves in a given binary tree. The function is a recursive implementation that traverses the entire tree to find and sum all the left leaf nodes.

Time Complexity

The time complexity of the sumOfLeftLeaves function is O(n), where n is the number of nodes in the binary tree. This is because the algorithm must visit each node exactly once to check if it is a left leaf node or not.

Space Complexity

The space complexity of the sumOfLeftLeaves function can be considered as O(h), where h is the height of the binary tree. This space is used for the recursive call stack. In the worst-case scenario (e.g., a completely unbalanced tree), the height of the tree can be n (the same as the number of nodes), and thus the space complexity can be O(n). However, in the best case (a completely balanced tree), the height of the tree is log(n), which results in a space complexity of O(log(n)).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know