404. Sum of Left Leaves
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 52.3%
Problem Breakdown
The problem requires finding the sum of all left leaves in a given binary tree. A left leaf is defined as a node that does not have any children (i.e., it is a leaf) and is located on the left side of its parent node.
Inputs:
- A binary tree represented by its root node.
Outputs:
- An integer representing the sum of all left leaves in the tree.
Implicit Constraints or Tricky Edge Cases:
- The tree could be empty (root is
None). - The tree could have only one node, which might not be a leaf.
- All nodes are assumed to have non-negative values.
Intuition
The brute-force approach would involve traversing the entire tree and checking each node to see if it is a left leaf. This would require visiting every node in the tree, leading to a time complexity of O(n), where n is the number of nodes in the tree. However, this approach does not leverage any specific properties of binary trees that could simplify the solution.
A better approach involves using a depth-first search (DFS) traversal, specifically a pre-order traversal, to efficiently identify left leaves. By keeping track of whether a node is a left child during the traversal, we can directly sum up the values of all left leaves without unnecessary checks.
Approach
We will use a recursive DFS approach to traverse the binary tree. The key insight is to pass an additional parameter indicating whether the current node is a left child. During the traversal:
- If the current node is
None, return 0. - If the current node is a leaf (i.e., it has no left or right children) and it is a left child, return its value.
- Recursively sum the values of left leaves in the left subtree by passing
Trueto indicate that the next node will be a left child. - Recursively sum the values of left leaves in the right subtree by passing
Falseto indicate that the next node will not be a left child.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once.
- Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack, which can go as deep as the height of the tree.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sumOfLeftLeaves(root: TreeNode) -> int:
def dfs(node: TreeNode, is_left: bool) -> int:
if not node:
return 0
if not node.left and not node.right:
return node.val if is_left else 0
left_sum = dfs(node.left, True)
right_sum = dfs(node.right, False)
return left_sum + right_sum
return dfs(root, False)
Edge Cases Handled
- Empty Tree: If the input tree is empty (
rootisNone), the function returns 0 immediately. - Single Node Tree: If the tree has only one node and it is not a leaf, the function returns 0. If it is a leaf, it returns its value if it is a left child (which it cannot be in this case since there are no other nodes).
- All Nodes as Left Leaves: The function correctly sums all left leaves regardless of their position in the tree.
- No Left Leaves: If there are no left leaves in the tree, the function returns 0.