Sum of the left leaves (Interview Way)

This article aims to explain how to solve the given problem during a technical interview. Let's assume that the interviewer expects to see your thought process and communicative skills, but not just final solution.

Note: the scenario below is very detailed. Combine/skip any steps if it is expected from you.

Problem

Given a binary tree. Calculate the sum of the left leaves

Example

 

Output: 7

Code Template

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/

public sealed class Solution
{
    public int LeftLeavesSum(TreeNode root)
    {
    }
}

1. Demonstrate understanding of the problem

• Give a definition of the term that is used in the problem - leaf : node without child nodes.
• Clarify an edge case to show your attention to details - the root node of a single-node tree is not considered a 'left leaf'.

2. Plan the solution

Describe the way you plan to follow:

• it is a binary-tree problem
• the program needs to visit every node
• let's use a tree traversal recursion algorithm

3. Start with something simple

Create a simple method that visits one node.

private void VisitNode(TreeNode root)
{
}

It is a recursion algorithm, so it should call child nodes:

private void VisitNode(TreeNode root)
{
    VisitNode(root.Left);
    VisitNode(root.Right);
}

Q: Does it matter which node goes first? A: No, because finally it calculates a single sum value.

The recursion should stop at some point. We may either check for root.Left != null before calling the VisitNode or to check it inside the method. The latter option looks better because it is just one check instead of two and it helps to handle initial condition as well. Be ready to explain performance impact of this choice - 2 additional method calls per a 'leaf' node.

private void VisitNode(TreeNode root)
{
    if (root == null)
    {
        return;
    }
    VisitNode(root.Left);
    VisitNode(root.Right);
}

The method does nothing at the moment. It should calculate the sum. There are 2 options to keep the sum value:

1. Use the method's return value.
2. Add an input parameter to the method. You may mention a few options your language supports here - like ref keyword in C# or an array int[]

You decide to use the former option because it is expected to give more readable code.

private int VisitNode(TreeNode root)
{
    if (root == null)
    {
        return 0;
    }
    return VisitNode(root.Left) + VisitNode(root.Right);
}

Let's add the leaf definition to the code.

private int VisitNode(TreeNode root)
{
    if (root == null)
    {
        return 0;
    }
    if (root.Left == null && root.Right == null)
    {
        return root.Value;
    }
    return VisitNode(root.Left) + VisitNode(root.Right);
}

What is the way to distinguish left leaves from right leaves? You could not do it inside the method, you don't have enough data. Let's add an input parameter.

private int VisitNode(TreeNode root, bool isLeft)
{
    if (root == null)
    {
        return 0;
    }
    if (root.Left == null && root.Right == null && isLeft)
    {
        return root.Value;
    }
    return VisitNode(root.Left, true) + VisitNode(root.Right, false);
}

It is the time to connect the main method with the VisitNode. Let's rename it by the way to something more meaningful, like Sum.

public int LeftLeavesSum(TreeNode root)
{
    return Sum(root, ?);
}

private int Sum(TreeNode root, bool isLeft)
{
    if (root == null)
    {
        return 0;
    }

    if (root.Left == null && root.Right == null && isLeft)
    {
        return root.Value;
    }

    return Sum(root.Left, true) + Sum(root.Right, false);
}

5. Think about edge cases

What should we put as the isLeft parameter for the root node? As you clarified at the start, the root node of a single-node tree is not a 'left leaf'. So the parameter should be false.

public int LeftLeavesSum(TreeNode root)
{
    return Sum(root, false);
}

private int Sum(TreeNode root, bool isLeft)
{
    if (root == null)
    {
        return 0;
    }

    if (root.Left == null && root.Right == null && isLeft)
    {
        return root.Value;
    }

    return Sum(root.Left, true) + Sum(root.Right, false);
}

Try to run the solution.

Correct? Great!

Error? Don't worry! It is an opportunity for you to demonstrate troubleshooting skills.

6. Improve

The solution is correct, it passes all the tests in appropriate time. Are there any ways to improve the solution? Think about performance and maintainability. The code still does extra calls to non-existing nodes passing null. Does it make sense to optimize it or readability is more important?

For example this way:

if (root.Left == null && root.Right == null)
{
    return isLeft ? root.Value : 0;
}

7. Display broad knowledge

Various options here depending on your knowledge/experience

• Use iteration instead of recursion -> performance impact -> Tail-call optimization
• Algorithm complexity