LeetCode: 404. Sum of Left Leaves

The Problem

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:

Input:  [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.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

int sumOfLeftLeaves(TreeNode* root) {
	return sumOfLeftLeaves(root, false);
}

int sumOfLeftLeaves(TreeNode* root, bool isLeft) {
    if(root == nullptr) return 0;

    TreeNode *left = root->left;
    TreeNode *right = root->right;

    if(isLeft && left == nullptr && right == nullptr)
    return root->val;
    return sumOfLeftLeaves(left, true) + sumOfLeftLeaves(right, false);
}

Here's how it works:

1. The function first checks if the root node is nullptr, which means it's a null node (no node). If it's null, the function returns 0, indicating that there's no sum to calculate.
2. It then retrieves the left and right children of the root node.
3. The function checks the isLeft parameter along with the left and right children to determine if the current node is a left leaf (a leaf node that's a left child of its parent and has no children itself). If these conditions are met, it returns the value of the current root node.
4. If the current node is not a left leaf, the function recursively calculates the sum of left leaves for its left child with sumOfLeftLeaves(left, true) (passing true to indicate it's a left child) and its right child with sumOfLeftLeaves(right, false) (passing false to indicate it's not a left child).
5. The final result is the sum of values of all left leaves in the subtree.

In the main function, sumOfLeftLeaves(root, false) is called, indicating that the root of the entire tree is not a left child. This initiates the process of calculating the sum of left leaves within the whole tree. The code uses recursion to traverse the tree and calculate the sum.