Sum of Left Leaves Leetcode Solutions

In this problem, we have to find the sum of all left leaves in a binary tree.  A leaf that is called a “Left Leaf” if it is a left child of any node in the tree.

Example  

     2
        
  /     \

4          7

        /      \

      9          4

Sum is 13

2

  \
 
    3

Sum is 0

Approach

We can use recursion to traverse the binary tree. If any node has a left child and it is a leaf too, we can add the value of the left child to our sum. But this approach uses the recursive stack space.

Can we use any other traversal that can save the memory space?

Morris Inorder Traversal can be implemented to visit every node iteratively. Check if it has a left leaf child and add its value accordingly in the result. This is the optimal approach. Note that we can implement “Morris Inorder traversal” only if the problem allows us to change the structure of the tree.

Algorithm(Recursive)

1. Create a function sumOfLeftLeaves() that returns the sum of left leaves of any passed root
2. If the root of the tree is NULL
   • return zero
3. If the current root has a left child and it is a leaf
   • return its value + sumOfLeftLEaves(root->left) + sumOfLeftLeaves(root->right)
4. Return sumOfLeftLEaves(root->left) + sumOfLeftLeaves(root->right)

Algorithm (Morris Inorder)

1. Traverse the binary using Morris Inorder Traversal:
   • Thread the inorder predecessor of the left subtree of any node to itself.
   • If a thread is already present, unthread it to retain the tree’s original structure.
2. If the left child of any node is a leaf, add it to the result.
3. Print the result.

Implementation

C++ Program of Sum of Left Leaves Leetcode Solutions

Recursive Approach

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    if(root)
    {
        if(root->left && !root->left->left && !root->left->right)
            return root->left->value + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
    return 0;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}

Optimal Method

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    int sum = 0;
    while(root != NULL)
    {
        if(root->left == NULL)
        {
            if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                sum += root->left->value;
            root = root->right;
        }
        else
        {
            treeNode* temp = root->left;
            while(temp->right != NULL && temp->right != root)
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = root;
                root = root->left;
            }
            else
            {
                temp->right = NULL;
                if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                    sum += root->left->value;
                root = root->right;
            }
        }
    }
    return sum;
}



int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}

Sum is 13

Java Program of Sum of Left Leaves Leetcode Solutions

Recursive Approach

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class sum_of_left_leaves
{
    public static int sumOfLeftLeaves(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left != null && root.left.left == null && root.left.right == null)
            return root.left.value + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(4);
        root.right = new treeNode(7);
        root.right.left = new treeNode(9);
        root.right.right =  new treeNode(4);

        System.out.println("Sum is " + sumOfLeftLeaves(root));
    }
}

Optimal Method

int sum = 0;
        while(root != null)
        {
            if(root.left == null)
            {
                if(root.left != null && root.left.left == null && root.left.right == null)
                    sum += root.left.value;
                root = root.right;
            }
            else
            {
                treeNode temp = root.left;
                while(temp.right != null && temp.right != root)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = root;
                    root = root.left;
                }
                else
                {
                    temp.right = null;
                    if(root.left != null && root.left.left == null && root.left.right == null)
                        sum += root.left.value;
                    root = root.right;
                }
            }
        }
        return sum;

Sum is 13

Complexity Analysis of Sum of Left Leaves Leetcode Solutions

Time Complexity

O(N), as we traverse the whole tree once in both recursive and iterative approach.

Space Complexity

O(1) using Morris Inorder Traversal. The recursive approach would take O(N) space in the memory.