404. Sum of Left Leaves

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.

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:

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

2. 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).

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

4. 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:

1if root.left and root.left.left is None and root.left.right is None:
2    res += root.left.val
3res += self.sumOfLeftLeaves(root.left)
4res += 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.

Example Walkthrough

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

Suppose we have the following binary tree:

1     3
2    / \
3   9  20
4     /  \
5    15   7

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

1. We start with the root node which has a value of 3. It's not a leaf, so we proceed to check its children.

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

3. Next, we explore the right child of the root, which is 20. It's not a leaf, so we need to traverse its children.

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

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

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

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.