algoadvance

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.

Example:

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.

Clarifying Questions

  1. Can the binary tree be empty?
    • Yes, in that case, the sum should be 0.
  2. What are the range of values for the node values and the number of nodes?
    • The number of nodes in the tree is in the range [1, 1000].
    • -1000 <= Node.val <= 1000.
  3. Are the nodes guaranteed to have unique values?
    • No, node values are not guaranteed to be unique.
  4. Can we assume the input is always a valid binary tree?
    • Yes, you can assume that the input is always a valid binary tree.

Strategy

To solve this problem, we can perform a traversal of the binary tree (using DFS or BFS) and check each node to see if it is a left leaf. If a node is determined to be a left leaf, we add its value to a running sum.

Steps:

  1. Define a Helper Function:
    • Create a helper function that will recursively traverse the tree.
    • This function should take an additional parameter to keep track of whether the current node is a left child.
  2. Recursive Traversal:
    • For each node, check if it is a left leaf:
      • If it is, add its value to the sum.
      • If not, continue traversing its children.
    • Sum the values of all left leaves.
  3. Edge Case Handling:
    • If the tree is empty, return 0.

Time Complexity

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        def is_leaf(node):
            return node is not None and node.left is None and node.right is None
        
        def dfs(node, is_left):
            if node is None:
                return 0
            if is_leaf(node) and is_left:
                return node.val
            return dfs(node.left, True) + dfs(node.right, False)
        
        return dfs(root, False)

# Example usage:
# root = TreeNode(3)
# root.left = TreeNode(9)
# root.right = TreeNode(20)
# root.right.left = TreeNode(15)
# root.right.right = TreeNode(7)
# solution = Solution()
# print(solution.sumOfLeftLeaves(root))  # Output: 24

Explanation

  1. TreeNode Class: Defined to provide the structure of each tree node.
  2. Solution Class:
    • The sumOfLeftLeaves function initializes the recursive dfs function.
    • The is_leaf helper function checks if a node is a leaf.
    • The dfs function traverses the tree, summing the values of left leaves:
      • It returns the node’s value if it is a left leaf.
      • Otherwise, it recursively sums the values of all left leaves in both the left and right subtrees.

By using the dfs function recursively, the solution ensures that all left leaves are identified and their values summed appropriately. This approach works efficiently within the constraints provided.

Try our interview co-pilot at AlgoAdvance.com