algoadvance

Leetcode 404. Sum of Left Leaves

Problem Statement

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 located on the left subtree of its parent.

Clarifying Questions

1. What are the properties of the tree?
   • The nodes of the tree can have any integer values.
   • The tree can contain negative, zero, or positive values.
2. What should we return if the tree is empty?
   • We should return 0.
3. Can the tree have duplicate values?
   • Yes, the values of nodes are not necessarily unique.
4. Is there a constraint on the depth or size of the tree?
   • There are no given constraints, but we need to consider efficiency in our solution.

Strategy

To solve this problem, we can use recursion:

1. Traverse the binary tree using a helper function.
2. During the traversal, check if the current node is a left leaf:
   • A node is a left leaf if it’s on the left subtree of its parent and it doesn’t have any children.
3. Sum up the values of all left leaves.
4. Return the computed sum.

Detailed Steps:

1. If the current node is null, return 0.
2. Check if the left child exists and is a leaf:
   • If it is, add its value to the sum.
   • Continue the traversal on both left and right subtrees.
3. Use a helper function to keep the main function clean.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return sumOfLeftLeavesHelper(root, false);
    }

    private int sumOfLeftLeavesHelper(TreeNode node, boolean isLeft) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null && isLeft) {
            return node.val;
        }
        return sumOfLeftLeavesHelper(node.left, true) + sumOfLeftLeavesHelper(node.right, false);
    }
}

Time Complexity

The time complexity of this solution is O(N) where N is the number of nodes in the tree.

• Each node is visited exactly once.
• This ensures that our solution is efficient and runs in linear time relative to the size of the tree.

Space Complexity

The space complexity is O(H) where H is the height of the binary tree.

• In the worst case (for a skewed tree), the recursion stack will contain all nodes, leading to O(N) space.
• In the average case (for a balanced tree), the height H is log(N), leading to O(log N) space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?