Is Sum of Left Leaves easy or hard?

Sum of Left Leaves is classified as an Easy problem on LeetCode with an acceptance rate above 60%. The challenge mainly involves correctly identifying a left leaf during tree traversal rather than implementing a complex algorithm.

Sum of Left Leaves Python/Java solution

Both Python and Java solutions typically implement DFS. In Python, recursion is commonly used with a helper function that checks whether a node's left child is a leaf. Java implementations follow the same logic using recursive methods or a stack-based traversal.

How to solve Sum of Left Leaves in O(n)?

Traverse the binary tree using DFS. At each node, check if the left child exists and whether that left child has no children. If both conditions hold, add its value to the total sum. Continue traversal through the remaining nodes so each node is processed once, resulting in O(n) time.

What is the best approach for Sum of Left Leaves?

Recursive Depth-First Search (DFS) is the most common and preferred approach. During traversal, check whether the current node's left child exists and is a leaf node. If it is, add its value to the sum; otherwise continue exploring both subtrees. This solution runs in O(n) time and O(h) space.

Is Sum of Left Leaves asked at Google/Amazon/Meta?

Tree traversal problems like Sum of Left Leaves frequently appear in technical interviews at companies such as Amazon, Google, and Meta. The problem tests your understanding of binary tree traversal, recursion, and identifying specific node conditions during traversal.

What data structure is used in Sum of Left Leaves?

The primary data structure is a binary tree. The algorithm typically uses depth-first search with either recursion (implicit call stack) or an explicit stack for iterative traversal.

What is the time complexity of Sum of Left Leaves?

The time complexity is O(n) because every node in the binary tree must be visited at least once to determine whether it forms a left leaf. Both recursive and iterative DFS solutions process each node exactly once.

Description Solution Video 6:10

404. Sum of Left Leaves

Easy63.1% acceptance6 companies

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.

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

Constraints:

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

Asked at 6 companies

Grammarly Microsoft Amazon Meta

Google Bloomberg

Topics

6:10

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,9,20,null,null,15,7]

Input

[1]

Your code is saved on this device.Solution