Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0404 - Sum of Left Leaves
    0404 - Sum of Left Leaves
    0404 - Sum of Left Leaves
    0404 - Sum of Left Leaves

    0404 - Sum of Left Leaves

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/sum-of-left-leaves/

    Solution 1 - Recursive DFS

    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 its parent. We traverse the tree recursively: at each node, check if the left child is a leaf — if so, add its value. Otherwise, recurse into both subtrees.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Iterative BFS

    Use a queue to traverse the tree level by level. At each node, check if the left child is a leaf and accumulate its value. This avoids recursion and uses an explicit queue instead of the call stack.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0404.1 - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """Binary Tree Node"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        """Sum of Left Leaves Function"""
        if not root:
            return 0

        total = 0

        # Check if left child is a leaf
        if root.left and not root.left.left and not root.left.right:
            total += root.left.val
        else:
            total += self.sumOfLeftLeaves(root.left)

        total += self.sumOfLeftLeaves(root.right)

        return total


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: [3,9,20,null,null,15,7] -> 24
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(Solution().sumOfLeftLeaves(root))  # 24

    # Example 2: [1] -> 0
    root2 = TreeNode(1)
    print(Solution().sumOfLeftLeaves(root2))  # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0404.2 - Solution 2 - Iterative BFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """Binary Tree Node"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        """Sum of Left Leaves Function"""
        if not root:
            return 0

        total = 0
        queue = deque([root])

        while queue:
            node = queue.popleft()

            if node.left:
                if not node.left.left and not node.left.right:
                    total += node.left.val
                else:
                    queue.append(node.left)

            if node.right:
                queue.append(node.right)

        return total


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: [3,9,20,null,null,15,7] -> 24
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(Solution().sumOfLeftLeaves(root))  # 24

    # Example 2: [1] -> 0
    root2 = TreeNode(1)
    print(Solution().sumOfLeftLeaves(root2))  # 0


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()