Sum of Left Leaves Algorithm Solution
This is a LeetCode numbered as a 404 Algorithm problem. I am providing an explanation and implementation in C++ for you. (Free of Charge)
In order to solve an algorithm problem, first, have an algorithm to solve an algorithm problem.
Step 1: Understand the problem
Step 2: Come up with brute force/naive solution
Step 3: Implement the naive solution
Step 4: Optimize the solution
Step 5: Implement the optimized solution
First things first,
Step 1: Understand the problem
Problem statement: Find the sum of all left leaves in a given binary tree.
Example:
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
This is a binary tree problem. Hence this called binary because every root have two (bi) child nodes and every child nodes could have two child nodes.
Step 2: Come up with brute force/naive solution and Step 4: Optimize the solution
Let’s use recursion to solve this problem because using iteration would be a hell of a task to do in an interview. As John Sonmez would (Writer of The Complete Software Developers Guide), “You need to manually be able to solve a problem before you can automate it.” So, when I solve this problem manually, I check the root node to make sure it is not pointing to nothin/NULL.
I want to go to the left root and see if that is a leaf. A node is a leaf node if both left and right child nodes of it are NULL/nothing. So I check the left root if it is a leaf if it is not then I add the value to the result. Well, if it is not a leaf, then I recursively go to step 1 and do the all good steps again and again until I am done with the left leaves.
When I am done with the left side of the tree then I recursively check the right side of the tree and go to step 1, and so forth to add the only left values to the result.
As for the leaf, the base case is to check the root is not NULL/nothing. I check the left and right of the root, is it pointing to nothing. Remember, we talked about the leaf concept, I am just writing the idea in code with an if statement.
Step 3: Implement the naive solution and Step 5: Implement the optimized solution
Timing Complexity analysis: This algorithm has the timing complexity of O(n) which is pretty good.
Have a go at it at Leetcode here.
Try to solve without looking at the solution.
class Solution {
public:
bool helpFunc(TreeNode * node)
{
if(node == NULL) return false;
if(node->left == NULL && node->right == NULL)
return true;
return false;
}
int sumOfLeftLeaves(TreeNode* root) {
int total = 0;
if(root != NULL){
if(helpFunc(root->left))
total += root->left->val;
else
total += sumOfLeftLeaves(root->left);
total += sumOfLeftLeaves(root->right);
}
return total;
}
};