Tutorialspoint.dev

Find sum of all left leaves in a given Binary Tree

Given a Binary Tree, find sum of all left leaves in it. For example, sum of all left leaves in below Binary Tree is 5+1=6.

tree



The idea is to traverse the tree, starting from root. For every node, check if its left subtree is a leaf. If it is, then add it to the result.

Following is the implementation of above idea.

C++

// A C++ program to find sum of all left leaves
#include <iostream>
using namespace std;
  
/* A binary tree Node has key, pointer to left and right
   children */
struct Node
{
    int key;
    struct Node* left, *right;
};
  
/* Helper function that allocates a new node with the
   given data and NULL left and right pointer. */
Node *newNode(char k)
{
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
  
// A utility function to check if a given node is leaf or not
bool isLeaf(Node *node)
{
   if (node == NULL)
       return false;
   if (node->left == NULL && node->right == NULL)
       return true;
   return false;
}
  
// This function returns sum of all left leaves in a given
// binary tree
int leftLeavesSum(Node *root)
{
    // Initialize result
    int res = 0;
  
    // Update result if root is not NULL
    if (root != NULL)
    {
       // If left of root is NULL, then add key of
       // left child
       if (isLeaf(root->left))
            res += root->left->key;
       else // Else recur for left child of root
            res += leftLeavesSum(root->left);
  
       // Recur for right child of root and update res
       res += leftLeavesSum(root->right);
    }
  
    // return result
    return res;
}
  
/* Driver program to test above functions*/
int main()
{
    // Let us a construct the Binary Tree
    struct Node *root         = newNode(20);
    root->left                = newNode(9);
    root->right               = newNode(49);
    root->right->left         = newNode(23);
    root->right->right        = newNode(52);
    root->right->right->left  = newNode(50);
    root->left->left          = newNode(5);
    root->left->right         = newNode(12);
    root->left->right->right  = newNode(12);
    cout << "Sum of left leaves is "
         << leftLeavesSum(root);
    return 0;
}

Java

// Java program to find sum of all left leaves
class Node 
{
    int data;
    Node left, right;
   
    Node(int item) 
    {
        data = item;
        left = right = null;
    }
}
   
class BinaryTree 
{
    Node root;
   
    // A utility function to check if a given node is leaf or not
    boolean isLeaf(Node node) 
    {
        if (node == null)
            return false;
        if (node.left == null && node.right == null)
            return true;
        return false;
    }
   
     // This function returns sum of all left leaves in a given
     // binary tree
    int leftLeavesSum(Node node) 
    {
        // Initialize result
        int res = 0;
   
        // Update result if root is not NULL
        if (node != null) 
        {
            // If left of root is NULL, then add key of
            // left child
            if (isLeaf(node.left))
                res += node.left.data;
            else // Else recur for left child of root
                res += leftLeavesSum(node.left);
   
            // Recur for right child of root and update res
            res += leftLeavesSum(node.right);
        }
   
        // return result
        return res;
    }
   
    // Driver program
    public static void main(String args[]) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(9);
        tree.root.right = new Node(49);
        tree.root.left.right = new Node(12);
        tree.root.left.left = new Node(5);
        tree.root.right.left = new Node(23);
        tree.root.right.right = new Node(52);
        tree.root.left.right.right = new Node(12);
        tree.root.right.right.left = new Node(50);
   
        System.out.println("The sum of leaves is " + 
                                       tree.leftLeavesSum(tree.root));
    }
}
   
// This code is contributed by Mayank Jaiswal 

Python

# Python program to find sum of all left leaves
  
# A Binary tree node
class Node:
    # Constructor to create a new Node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
  
# A utility function to check if a given node is leaf or not
def isLeaf(node):
    if node is None:
        return False
    if node.left is None and node.right is None:
        return True
    return False
  
# This function return sum of all left leaves in a
# given binary tree
def leftLeavesSum(root):
  
    # Initialize result
    res = 0
      
    # Update result if root is not None
    if root is not None:
  
        # If left of root is None, then add key of
        # left child
        if isLeaf(root.left):
            res += root.left.key
        else:
            # Else recur for left child of root
            res += leftLeavesSum(root.left)
  
        # Recur for right child of root and update res
        res += leftLeavesSum(root.right)
    return res
  
# Driver program to test above function 
  
# Let us constrcut the Binary Tree shown in the above function
root = Node(20)
root.left = Node(9)
root.right = Node(49)
root.right.left = Node(23)        
root.right.right = Node(52)
root.right.right.left = Node(50)
root.left.left = Node(5)
root.left.right = Node(12)
root.left.right.right = Node(12)
print "Sum of left leaves is", leftLeavesSum(root)
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

using System;
  
// C# program to find sum of all left leaves 
public class Node
{
    public int data;
    public Node left, right;
  
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
  
public class BinaryTree
{
    public Node root;
  
    // A utility function to check if a given node is leaf or not 
    public virtual bool isLeaf(Node node)
    {
        if (node == null)
        {
            return false;
        }
        if (node.left == null && node.right == null)
        {
            return true;
        }
        return false;
    }
  
     // This function returns sum of all left leaves in a given 
     // binary tree 
    public virtual int leftLeavesSum(Node node)
    {
        // Initialize result 
        int res = 0;
  
        // Update result if root is not NULL 
        if (node != null)
        {
            // If left of root is NULL, then add key of 
            // left child 
            if (isLeaf(node.left))
            {
                res += node.left.data;
            }
            else // Else recur for left child of root
            {
                res += leftLeavesSum(node.left);
            }
  
            // Recur for right child of root and update res 
            res += leftLeavesSum(node.right);
        }
  
        // return result 
        return res;
    }
  
    // Driver program 
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(9);
        tree.root.right = new Node(49);
        tree.root.left.right = new Node(12);
        tree.root.left.left = new Node(5);
        tree.root.right.left = new Node(23);
        tree.root.right.right = new Node(52);
        tree.root.left.right.right = new Node(12);
        tree.root.right.right.left = new Node(50);
  
        Console.WriteLine("The sum of leaves is " + tree.leftLeavesSum(tree.root));
    }
}
  
  //  This code is contributed by Shrikant13


Output: 

Sum of left leaves is 78

Time complexity of the above solution is O(n) where n is number of nodes in Binary Tree.

Following is Another Method to solve the above problem. This solution passes in a sum variable as an accumulator. When a left leaf is encountered, the leaf’s data is added to sum. Time complexity of this method is also O(n). Thanks to Xin Tong (geeksforgeeks userid trent.tong) for suggesting this method.

C++

// A C++ program to find sum of all left leaves
#include <iostream>
using namespace std;
  
/* A binary tree Node has key, pointer to left and right
   children */
struct Node
{
    int key;
    struct Node* left, *right;
};
  
/* Helper function that allocates a new node with the
   given data and NULL left and right pointer. */
Node *newNode(char k)
{
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
  
/* Pass in a sum variable as an accumulator */
void leftLeavesSumRec(Node *root, bool isleft, int *sum)
{
    if (!root) return;
  
    // Check whether this node is a leaf node and is left.
    if (!root->left && !root->right && isleft)
        *sum += root->key;
  
    // Pass 1 for left and 0 for right
    leftLeavesSumRec(root->left,  1, sum);
    leftLeavesSumRec(root->right, 0, sum);
}
  
// A wrapper over above recursive function
int leftLeavesSum(Node *root)
{
    int sum = 0; //Initialize result
  
    // use the above recursive function to evaluate sum
    leftLeavesSumRec(root, 0, &sum);
  
    return sum;
}
  
/* Driver program to test above functions*/
int main()
{
    // Let us construct the Binary Tree shown in the
    // above figure
    int sum = 0;
    struct Node *root         = newNode(20);
    root->left                = newNode(9);
    root->right               = newNode(49);
    root->right->left         = newNode(23);
    root->right->right        = newNode(52);
    root->right->right->left  = newNode(50);
    root->left->left          = newNode(5);
    root->left->right         = newNode(12);
    root->left->right->right  = newNode(12);
  
    cout << "Sum of left leaves is " << leftLeavesSum(root) << endl;
    return 0;
}

Java

// Java program to find sum of all left leaves
class Node 
{
    int data;
    Node left, right;
   
    Node(int item) {
        data = item;
        left = right = null;
    }
}
   
// Passing sum as accumulator and implementing pass by reference 
// of sum variable 
class Sum 
{
    int sum = 0;
}
   
class BinaryTree 
{
    Node root;
   
    /* Pass in a sum variable as an accumulator */
    void leftLeavesSumRec(Node node, boolean isleft, Sum summ) 
    {
        if (node == null)
            return;
   
        // Check whether this node is a leaf node and is left.
        if (node.left == null && node.right == null && isleft)
            summ.sum = summ.sum + node.data;
   
        // Pass true for left and false for right
        leftLeavesSumRec(node.left, true, summ);
        leftLeavesSumRec(node.right, false, summ);
    }
   
    // A wrapper over above recursive function
    int leftLeavesSum(Node node) 
    {
        Sum suum = new Sum();
          
        // use the above recursive function to evaluate sum
        leftLeavesSumRec(node, false, suum);
   
        return suum.sum;
    }
   
    // Driver program
    public static void main(String args[]) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(9);
        tree.root.right = new Node(49);
        tree.root.left.right = new Node(12);
        tree.root.left.left = new Node(5);
        tree.root.right.left = new Node(23);
        tree.root.right.right = new Node(52);
        tree.root.left.right.right = new Node(12);
        tree.root.right.right.left = new Node(50);
   
        System.out.println("The sum of leaves is " + 
                                    tree.leftLeavesSum(tree.root));
    }
}
   
// This code is contributed by Mayank Jaiswal 

Python

# Python program to find sum of all left leaves
  
# A binary tree node
class Node:
  
    # A constructor to create a new Node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
  
def leftLeavesSumRec(root, isLeft, summ):
    if root is None:
        return
      
    # Check whether this node is a leaf node and is left
    if root.left is None and root.right is None and isLeft == True:
        summ[0] += root.key
  
    # Pass 1 for left and 0 for right
    leftLeavesSumRec(root.left, 1, summ)
    leftLeavesSumRec(root.right, 0, summ)
      
  
# A wrapper over above recursive function
def leftLeavesSum(root):
    summ = [0] # initialize result
      
    # Use the above recursive fucntion to evaluate sum
    leftLeavesSumRec(root, 0, summ)
      
    return summ[0]
  
# Driver program to test above function
  
# Let us construct the Binary Tree shown in the
# above figure
root = Node(20);
root.left= Node(9);
root.right   = Node(49);
root.right.left = Node(23);
root.right.right= Node(52);
root.right.right.left  = Node(50);
root.left.left  = Node(5);
root.left.right = Node(12);
root.left.right.right  = Node(12);
  
print "Sum of left leaves is", leftLeavesSum(root)  
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

using System;
  
// C# program to find sum of all left leaves 
public class Node
{
    public int data;
    public Node left, right;
  
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
  
// Passing sum as accumulator and implementing pass by reference  
// of sum variable  
public class Sum
{
    public int sum = 0;
}
  
public class BinaryTree
{
    public Node root;
  
    /* Pass in a sum variable as an accumulator */
    public virtual void leftLeavesSumRec(Node node, bool isleft, Sum summ)
    {
        if (node == null)
        {
            return;
        }
  
        // Check whether this node is a leaf node and is left. 
        if (node.left == null && node.right == null && isleft)
        {
            summ.sum = summ.sum + node.data;
        }
  
        // Pass true for left and false for right 
        leftLeavesSumRec(node.left, true, summ);
        leftLeavesSumRec(node.right, false, summ);
    }
  
    // A wrapper over above recursive function 
    public virtual int leftLeavesSum(Node node)
    {
        Sum suum = new Sum();
  
        // use the above recursive function to evaluate sum 
        leftLeavesSumRec(node, false, suum);
  
        return suum.sum;
    }
  
    // Driver program 
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(9);
        tree.root.right = new Node(49);
        tree.root.left.right = new Node(12);
        tree.root.left.left = new Node(5);
        tree.root.right.left = new Node(23);
        tree.root.right.right = new Node(52);
        tree.root.left.right.right = new Node(12);
        tree.root.right.right.left = new Node(50);
  
        Console.WriteLine("The sum of leaves is " + tree.leftLeavesSum(tree.root));
    }
}
  
  // This code is contributed by Shrikant13


Output: 

Sum of left leaves is 78

 
Iterative Approach :
This is the Iterative Way to find the sum of the left leaves.
Idea is to perform Depth-First Traversal on the tree (either Inorder, Preorder or Postorder) using a stack and checking if the Left Child is a Leaf node. If it is, then add the nodes value to the sum variable

# Python program to find sum of all left leaves
  
# A binary tree node
class Node:
  
    # A constructor to create a new Node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
  
  
# Return the sum of left leaf nodes
def sumOfLeftLeaves(root):
    if(root is None):
        return
      
    # Using a stack for Depth-First Traversal of the tree
    stack = []   
    stack.append(root)
      
    # sum holds the sum of all the left leaves
    sum = 0
  
    while len(stack) > 0:
        currentNode = stack.pop()
  
        if currentNode.left is not None:
            stack.append(currentNode.left)
              
            # Check if currentNode's left child is a leaf node
            if currentNode.left.left is None and currentNode.left.right is None:
  
                # if currentNode is a leaf, add its data to the sum  
                sum = sum + currentNode.left.data 
  
        if currentNode.right is not None:
            stack.append(currentNode.right)
    return sum
  
# Driver Code
root = Tree(20);
root.left= Tree(9);
root.right   = Tree(49);
root.right.left = Tree(23);
root.right.right= Tree(52);
root.right.right.left  = Tree(50);
root.left.left  = Tree(5);
root.left.right = Tree(12);
root.left.right.right  = Tree(12);
  
print('Sum of left leaves is {}'.format(sumOfLeftLeaves(root)))

Output: 

Sum of left leaves is 78

Thanks to Shubham Tambere for suggesting this approach.



This article is attributed to GeeksforGeeks.org

tags:

Tree Traversal Traversal Tree
Prev Next
More topics on Binary Tree Data Structure

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Binary Tree Data S... Applications of tree data stru...
Binary Tree Data S... Expression Tree
Binary Tree Data S... Evaluation of Expression Tree
Binary Tree Data S... Program to count leaf nodes in...
Binary Tree Data S... Inorder Tree Traversal without...
Binary Tree Data S... Tree Traversals (Inorder, Preo...