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 that is the left child of its parent.

Clarifying Questions

1. What is the structure of the tree node?
   • The tree node is typically represented by a structure like the following:

     struct TreeNode {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode() : val(0), left(nullptr), right(nullptr) {}
         TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
         TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     };
     

2. Can the tree be empty?
   • Yes, the tree can be empty. In such a case, the sum should be 0.
3. Is it important to consider both left and right subtrees?
   • Yes, we need to traverse the entire tree to check for left leaves.

Strategy

We’ll use a recursive depth-first search (DFS) approach to traverse the binary tree. At each node, we’ll check if the left child is a leaf. If it is, we’ll add its value to our sum. We also need to continue traversing both left and right subtrees to ensure we capture all left leaves in the tree.

Steps:

1. Create a helper function that takes a node and a boolean to indicate if the node is a left child.
2. In the helper function:
   • If the node is nullptr, return 0.
   • If the node is a leaf (both children are nullptr) and the boolean indicates it is a left child, return the node value.
   • Recursively call the helper function for both left and right children.
3. The main function will call this helper function with the root node and an initial boolean value of false (since the root is not a left child).

Code

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        return dfs(root, false);
    }

private:
    int dfs(TreeNode* node, bool isLeft) {
        if (!node) return 0;
        if (!node->left && !node->right) {
            if (isLeft) return node->val;  // only include left leaves
            return 0;
        }
        return dfs(node->left, true) + dfs(node->right, false);
    }
};

Time Complexity

• The time complexity is (O(n)), where (n) is the number of nodes in the tree. This is because in the worst case, we have to visit every node once.

• The space complexity is (O(h)), where (h) is the height of the tree. This is due to the recursion stack for a DFS, which can vary from (O(\log n)) in a balanced tree to (O(n)) in the worst case (skewed tree).

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?