Sum of Left Leaves Algorithm Solution Version 2 in C++
Sum of left leaves is a popular coding question for an interview. It’s a Facebook Coding Interview Question and also asked by other top tech companies. It’s a must algorithm problem to know for software engineer.
To solve an algorithm problem, I highly recommend to have an algorithm to solve an algorithm problems. Algorithm is nothing but steps. The steps you take to do a task. For example, think of the steps you take to go to work.
The steps I will follow in this post are,
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
Step 1: Understand the problem well
The Problem statement: Find the sum of all left leaves in a given binary tree.
Example: Problem A,
3 / \ 9 20 / \ 15 7
The number 3 are called head or root node. The number 9 is left of the head and 15 is left of 20. So, there are two left leaves in the binary tree, with values 9 and 15 respectively. They values are marked green for readability.
Let’s deep down into the problem. We would add the left leaves only, 9 is the left of the root 3, so we add 9 to our result. Now our result is 9 so far. The value 20 is right of root/head node but the left of 20 is 15 which is what we are looking for. So we would add 15 to our result. So our result = 9 + 15 = 24.
Problem B:
3 / \ 9 20 / \ 7 7
So let’s look at another example, so we understand the problem better. We are adding the left leaves only, so 9 is left of the root, we add 9 to the result, and 9 does not have any children node, therefore we done with the left side of 9. Now, the right of root or value 3 is 20 and left of 20 is 7. So we would add 7 to the result. Our result is 9 + 7 = 16.
A quick note: The question format of Problem A and B are called binary search tree (BST) problem. Hence it called binary because every root has two (bi) child nodes and every child nodes could have two child nodes and so forth in an ideal case.
Step 2: Come up with brute force/naive solution
Note: A node is a leaf node if both left and right child nodes of it are empty.
Let’s use recursion to solve this problem. As Tech Terms defined recursive function as, “… a function that calls itself during its execution.”
First, I check for the root and make sure the root is not empty because if the root or head node is empty then there is nothing to add to the result. In a recursive function this is called base case.
Second, I go to the left root, and check if this is a leaf node? If it is a leaf, I add the value to a temporary result variable. A node is a leaf node, if and only if the node have no children node.
Third, Let’s suppose it is not a leaf node, what do we do? We call the recursive function to go back to the root of the left tree.
Finally, since we have finished adding the left values of the tree to result, we call the recursive function on the right side. Magically, that function goes at the beginning of the first step and does it until it finds a leaf.
Step 3: Implement the naive solution
It is a good practice to write the pseudo-code before actually start coding. I found this extremely helpful.
Let’s create a helper function that checks if the tree is a leaf.
bool isItLeaf ( Node)
The base case for our recursive function
Is the node empty
Return false
Is the right and left empty
Return true
Every other case, return false because if we are here then for sure we know that the tree is not a leaf. The problem wants an integer value to return, so our return type is an int. This is the sumOfLeftLeaves function
int sumOfLeftLeaves(root)
We check the left of the root first
isItLeaf (left of root is true)
If there is something add this value to a temporary variable
isItLeaf (left of root is not true)
Call the recursive sumOfLeftLeaves on the root left
Timing Complexity analysis: This algorithm has the timing complexity of O(n) which is okay. It could be better.
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;
}
};Have a go at it at Leetcode here.
The GitHub link is here. Look at my previous solution.
Please let me know, if this was helpful.