Leetcode – Sum of Left Leaves Solution in Python

Spread the love

Introduction

In this detailed article, we’ll delve into the ‘Sum of Left Leaves’ problem on Leetcode, discuss different approaches to solve it in Python, analyze the time complexity, and understand the underlying concepts.

Problem Statement

The ‘Sum of Left Leaves’ problem is listed as problem number 404 on Leetcode. The problem statement is as follows:

Find the sum of all left leaves in a given binary tree.

A leaf node is defined as a node that does not have any children (i.e., it doesn’t have left and right child nodes).

Example:

    3
   / \
  9  20
    /  \
   15   7

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, hence sum = 24.

Approach 1: Recursive Depth-First Search (DFS)

  1. Define a recursive function dfs that takes a node and a boolean flag indicating whether it is a left child node.
  2. For a null node, return 0 as the sum.
  3. For a leaf node that is a left child, return the value of the node.
  4. For other nodes, recursively call the dfs function for the left child with the left flag set to True and for the right child with the left flag set to False, and return the sum of the two calls.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumOfLeftLeaves(root):
    def dfs(node, is_left):
        if not node:
            return 0
        if not node.left and not node.right:
            return node.val if is_left else 0
        return dfs(node.left, True) + dfs(node.right, False)
    
    return dfs(root, False)

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree, as it traverses through each node once.

Approach 2: Iterative Depth-First Search (DFS) using Stack

  1. Use a stack to simulate the recursive stack used in DFS.
  2. Push the root node and a flag indicating whether it is a left child into the stack.
  3. While the stack is not empty, pop a node and the left flag. If it’s a left leaf node, add its value to the sum.
  4. Push the left and right children of the current node into the stack with appropriate flags.
def sumOfLeftLeaves(root):
    if not root:
        return 0
    
    stack = [(root, False)]
    sum_left_leaves = 0
    
    while stack:
        node, is_left = stack.pop()
        if is_left and not node.left and not node.right:
            sum_left_leaves += node.val
        
        if node.left:
            stack.append((node.left, True))
        if node.right:
            stack.append((node.right, False))
    
    return sum_left_leaves

Time Complexity

This approach also has a time complexity of O(n) since it visits each node once.

Conclusion

The ‘Sum of Left Leaves’ problem on Leetcode deals with finding the sum of all left leaf nodes in a binary tree. This can be effectively solved using depth-first search, either recursively or iteratively. The recursive approach is more intuitive and easier to implement, while the iterative approach using a stack simulates the recursive behavior without the function call stack. Both approaches have a linear time complexity of O(n), where n is the number of nodes in the tree. Understanding the structure of binary trees and traversal techniques is crucial in solving such problems efficiently.

Leave a Reply