How do you solve Sum of Left Leaves on LeetCode?

Sum of Left Leaves (LeetCode #404) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Understanding the structure of binary trees is crucial.

What is the brute force solution for Sum of Left Leaves?

The brute force approach for Sum of Left Leaves is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves traversing the entire tree and checking each node to see if it's a left leaf. This is straightforward but inefficient as it may require multiple passes through the tree. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Sum of Left Leaves?

Sum of Left Leaves uses the following concepts: Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Recursion.

What are the interview tips for Sum of Left Leaves?

Always clarify the definition of terms like 'leaf' and 'left leaf' with the interviewer. Consider edge cases, such as trees with only one node. Discuss your thought process and approach before jumping into coding.

What are common mistakes when solving Sum of Left Leaves?

Not checking if a node is null before accessing its children. Confusing left leaves with all leaves.

#404

Sum of Left Leaves

Easy

TreeDepth-First SearchBreadth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach uses a single traversal of the tree while keeping track of whether a node is a left child. This avoids unnecessary checks and reduces the time complexity significantly.

⚙️

Algorithm

4 steps

1Step 1: Use a depth-first search (DFS) approach, passing a boolean indicating whether the current node is a left child.
2Step 2: If the current node is null, return 0.
3Step 3: If the current node is a left leaf (it has no children), return its value.
4Step 4: Recursively call the function for the left and right children, summing the results.

solution.py13 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def sumOfLeftLeaves(root, is_left=False):
9    if not root:
10        return 0
11    if not root.left and not root.right and is_left:
12        return root.val
13    return sumOfLeftLeaves(root.left, True) + sumOfLeftLeaves(root.right, False)

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Understanding the structure of binary trees is crucial.
2Recognizing leaf nodes and their relationships helps in solving tree problems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.