Jobs

Interviews

Discussions

Sum of Left Leaves

Easy

Microsoft

0 views

Topics:

TreesRecursion

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

Sum of Left Leaves

Easy

Microsoft

0 views

Topics:

TreesRecursion

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree be empty? If so, what should I return?
What is the range of values for the nodes in the binary tree?
Is a single node considered a leaf?
Should I assume the input is a valid binary tree, or should I handle cases with cycles or other invalid structures?
Can the tree contain duplicate values, and if so, how does that affect the sum of left leaves?

Brute Force Solution

Approach

We need to find the sum of all the left 'leaves' in a tree. The brute force way is to look at every single part of the tree and check if it is a left leaf, and if so, add its value to the running total.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Check if the left branch exists.
If the left branch does exist, determine if this left branch is a 'leaf' (meaning it has no further branches).
If it's a left leaf, remember its value by adding it to a running total.
Now, whether or not the left branch was a leaf, go down the left branch and repeat this whole checking process again.
After checking everything on the left side, do the exact same process on the right side of the tree.
Continue doing this until you have checked every single branch and leaf in the entire tree.
The final running total is the answer: the sum of all the left leaves.

Code Implementation

def sum_of_left_leaves_brute_force(root):
    total_sum = 0
    
    if root is None:
        return total_sum

    # Check if a left branch exists.
    if root.left:

        # Check if the left child is a leaf node.
        if root.left.left is None and root.left.right is None:
            total_sum += root.left.val

        total_sum += sum_of_left_leaves_brute_force(root.left)

    # Recursively call the function on the right subtree
    total_sum += sum_of_left_leaves_brute_force(root.right)

    return total_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node of the tree exactly once. For each node, a constant amount of work is performed, which involves checking if the left child exists and if it's a leaf. Since the number of nodes visited is proportional to the number of nodes n in the tree, the time complexity is O(n).

Space Complexity

O(H) – The algorithm uses recursion. In the worst-case scenario, where the tree is highly skewed (e.g., a linked list), the recursion depth can be equal to the height (H) of the tree. Each recursive call adds a new frame to the call stack. Therefore, the auxiliary space used by the call stack is proportional to the tree's height H, where in the worst case H equals the number of nodes, N. Consequently, the space complexity is O(H).

Optimal Solution

Approach

To efficiently find the sum of left leaves, we'll use a simple tree traversal. The key is to only add the value of a node if it is both a leaf and a left child of its parent.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Check if the node to the left exists. If it does, look to see if it is a leaf (meaning it has no children of its own).
If the left node is a leaf, add its value to our running total.
Continue this process by moving down the tree to the left node and then to the right node, if they exist, repeating the check for left leaves at each step.
When you've checked every part of the tree, the running total will be the sum of all the left leaves.

Code Implementation

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

def sum_of_left_leaves(root: TreeNode) -> int:
    total_sum = 0

    def traverse_tree(node: TreeNode, is_left: bool):
        nonlocal total_sum
        if not node:
            return

        # Check if the current node is a leaf node.
        if not node.left and not node.right and is_left:
            total_sum += node.val
            return

        # Traverse to the left child.
        if node.left:

            traverse_tree(node.left, True)

        # Traverse to the right child.
        if node.right:

            # Right child is never a left node.
            traverse_tree(node.right, False)

    # Initiate traversal from the root.
    traverse_tree(root, False)

    return total_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The provided solution performs a tree traversal, visiting each node in the binary tree at most once. The time complexity is directly proportional to the number of nodes in the tree, denoted by n. At each node, a constant amount of work is performed (checking if the left child exists and is a leaf). Therefore, the overall time complexity is O(n), where n is the number of nodes in the tree. This is because the algorithm explores each node in the tree a constant number of times.

Space Complexity

O(N) – The provided solution uses a tree traversal algorithm that, in the worst-case scenario of a skewed tree (where each node only has a left or right child), will recursively call the function for each node in the tree. This recursive process creates stack frames. Therefore, the auxiliary space used is proportional to the height of the tree. In the worst-case scenario the height of the tree is equal to N where N is the number of nodes. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty tree (root is null)	Return 0 immediately, as there are no nodes, and therefore no left leaves.
Tree with only a root node	Return 0, as a single root node cannot have any children (left or otherwise).
Tree with a root and only a left child that is a leaf	The solution should correctly identify this single left leaf and return its value.
Tree with a root and only a right child that is a leaf	Return 0, as we are only concerned with left leaves.
A left child that is not a leaf	The solution should traverse further down the tree and not count the value of this non-leaf node in the sum.
Large, deeply unbalanced tree	The recursive solution should be mindful of potential stack overflow issues and consider an iterative solution using a stack if needed to prevent it.
Tree with negative values	The solution should handle negative node values correctly, simply adding them to the sum if they are left leaves.
Tree with a left leaf having value zero	The solution should correctly include zero in the sum when it encounters a left leaf with value zero.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree be empty? If so, what should I return?
What is the range of values for the nodes in the binary tree?
Is a single node considered a leaf?
Should I assume the input is a valid binary tree, or should I handle cases with cycles or other invalid structures?
Can the tree contain duplicate values, and if so, how does that affect the sum of left leaves?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Check if the left branch exists.
If the left branch does exist, determine if this left branch is a 'leaf' (meaning it has no further branches).
If it's a left leaf, remember its value by adding it to a running total.
Now, whether or not the left branch was a leaf, go down the left branch and repeat this whole checking process again.
After checking everything on the left side, do the exact same process on the right side of the tree.
Continue doing this until you have checked every single branch and leaf in the entire tree.
The final running total is the answer: the sum of all the left leaves.

Code Implementation

def sum_of_left_leaves_brute_force(root):
    total_sum = 0
    
    if root is None:
        return total_sum

    # Check if a left branch exists.
    if root.left:

        # Check if the left child is a leaf node.
        if root.left.left is None and root.left.right is None:
            total_sum += root.left.val

        total_sum += sum_of_left_leaves_brute_force(root.left)

    # Recursively call the function on the right subtree
    total_sum += sum_of_left_leaves_brute_force(root.right)

    return total_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To efficiently find the sum of left leaves, we'll use a simple tree traversal. The key is to only add the value of a node if it is both a leaf and a left child of its parent.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Check if the node to the left exists. If it does, look to see if it is a leaf (meaning it has no children of its own).
If the left node is a leaf, add its value to our running total.
Continue this process by moving down the tree to the left node and then to the right node, if they exist, repeating the check for left leaves at each step.
When you've checked every part of the tree, the running total will be the sum of all the left leaves.

Code Implementation

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

def sum_of_left_leaves(root: TreeNode) -> int:
    total_sum = 0

    def traverse_tree(node: TreeNode, is_left: bool):
        nonlocal total_sum
        if not node:
            return

        # Check if the current node is a leaf node.
        if not node.left and not node.right and is_left:
            total_sum += node.val
            return

        # Traverse to the left child.
        if node.left:

            traverse_tree(node.left, True)

        # Traverse to the right child.
        if node.right:

            # Right child is never a left node.
            traverse_tree(node.right, False)

    # Initiate traversal from the root.
    traverse_tree(root, False)

    return total_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree (root is null)	Return 0 immediately, as there are no nodes, and therefore no left leaves.
Tree with only a root node	Return 0, as a single root node cannot have any children (left or otherwise).
Tree with a root and only a left child that is a leaf	The solution should correctly identify this single left leaf and return its value.
Tree with a root and only a right child that is a leaf	Return 0, as we are only concerned with left leaves.
A left child that is not a leaf	The solution should traverse further down the tree and not count the value of this non-leaf node in the sum.
Large, deeply unbalanced tree	The recursive solution should be mindful of potential stack overflow issues and consider an iterative solution using a stack if needed to prevent it.
Tree with negative values	The solution should handle negative node values correctly, simply adding them to the sum if they are left leaves.
Tree with a left leaf having value zero	The solution should correctly include zero in the sum when it encounters a left leaf with value zero.