Sum of all leaf nodes of binary tree

Given a binary tree, find the sum of all the leaf nodes.

Examples:

Input : 
        1
      /   
     2     3
    /    / 
   4   5 6   7
          
           8
Output :
Sum = 4 + 5 + 8 + 7 = 24

The idea is to traverse the tree in any fashion and check if the node is the leaf node or not. If the node is the leaf node, add node data to sum variable.

Following is the implementation of above approach.

C++

// CPP program to find sum of 
// all leaf nodes of binary tree 
#include<bits/stdc++.h> 
using namespace std; 
  
// struct binary tree node 
struct Node{ 
    int data; 
    Node *left, *right; 
}; 
  
// return new node  
Node *newNode(int data){ 
    Node *temp = new Node(); 
    temp->data = data; 
    temp->left = temp->right = NULL; 
} 
  
// utility function which calculates 
// sum of all leaf nodes 
void leafSum(Node *root, int *sum){ 
    if (!root) 
        return; 
  
    // add root data to sum if  
    // root is a leaf node 
    if (!root->left && !root->right) 
        *sum += root->data; 
  
    // propagate recursively in left 
    // and right subtree 
    leafSum(root->left, sum); 
    leafSum(root->right, sum); 
} 
  
// driver program 
int main(){ 
      
    //contruct binary tree 
    Node *root = newNode(1); 
    root->left = newNode(2); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->right = newNode(3); 
    root->right->right = newNode(7); 
    root->right->left = newNode(6); 
    root->right->left->right = newNode(8); 
      
    // variable to store sum of leaf nodes 
    int sum = 0; 
    leafSum(root, &sum); 
    cout << sum << endl; 
    return 0; 
} 

Java

// Java program to find sum of 
// all leaf nodes of binary tree 
public class GFG { 
   
    // user define class node 
    static class Node{ 
        int data; 
        Node left, right; 
          
        // constructor 
        Node(int data){ 
            this.data = data; 
            left = null; 
            right = null; 
        } 
    } 
      
    static int sum; 
      
    // utility function which calculates 
    // sum of all leaf nodes 
    static void leafSum(Node root){ 
        if (root == null) 
            return; 
       
        // add root data to sum if  
        // root is a leaf node 
        if (root.left == null && root.right == null) 
            sum += root.data; 
       
        // propagate recursively in left 
        // and right subtree 
        leafSum(root.left); 
        leafSum(root.right); 
    } 
       
    // driver program 
    public static void main(String args[]) 
    { 
        //contruct binary tree 
        Node root = new Node(1); 
        root.left = new Node(2); 
        root.left.left = new Node(4); 
        root.left.right = new Node(5); 
        root.right = new Node(3); 
        root.right.right = new Node(7); 
        root.right.left = new Node(6); 
        root.right.left.right = new Node(8); 
           
        // variable to store sum of leaf nodes 
        sum = 0; 
        leafSum(root); 
        System.out.println(sum); 
    } 
} 
// This code is contributed by Sumit Ghosh 

Python3

# Python3 Program to find the  
#sum of leaf nodes of a binary tree 
  
  
 # Class for node creation 
class Node: 
      
     # Constructor 
    def __init__(self, data):              
        self.data = data 
        self.left = None
        self.right = None
  
# Utility function to calculate  
# the sum of all leaf nodes 
def leafSum(root): 
    global total 
    if root is None: 
        return
    if (root.left is None and root.right is None): 
        total += root.data 
    leafSum(root.left) 
    leafSum(root.right) 
  
# Binary tree Fromation 
if __name__=='__main__': 
    root = Node(1) 
    root.left = Node(2) 
    root.left.left = Node(4) 
    root.left.right = Node(5) 
    root.right = Node(3) 
    root.right.right = Node(7) 
    root.right.left = Node(6) 
    root.right.left.right = Node(8) 
# Variable to store the sum of leaf nodes 
    total = 0
    leafSum(root) 
# Printing the calculated sum 
    print(total) 
  
# This code is contributed by Naren Sai Krishna 

C#

using System; 
  
// C# program to find sum of  
// all leaf nodes of binary tree  
public class GFG 
{ 
  
    // user define class node  
    public class Node 
    { 
        public int data; 
        public Node left, right; 
  
        // constructor  
        public Node(int data) 
        { 
            this.data = data; 
            left = null; 
            right = null; 
        } 
    } 
  
    public static int sum; 
  
    // utility function which calculates  
    // sum of all leaf nodes  
    public static void leafSum(Node root) 
    { 
        if (root == null) 
        { 
            return; 
        } 
  
        // add root data to sum if   
        // root is a leaf node  
        if (root.left == null && root.right == null) 
        { 
            sum += root.data; 
        } 
  
        // propagate recursively in left  
        // and right subtree  
        leafSum(root.left); 
        leafSum(root.right); 
    } 
  
    // driver program  
    public static void Main(string[] args) 
    { 
        //contruct binary tree  
        Node root = new Node(1); 
        root.left = new Node(2); 
        root.left.left = new Node(4); 
        root.left.right = new Node(5); 
        root.right = new Node(3); 
        root.right.right = new Node(7); 
        root.right.left = new Node(6); 
        root.right.left.right = new Node(8); 
  
        // variable to store sum of leaf nodes  
        sum = 0; 
        leafSum(root); 
        Console.WriteLine(sum); 
    } 
} 
  
  // This code is contributed by Shrikant13 

Output:

Time Complexity : O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Sum of all leaf nodes of binary tree

C++

Java

Python3

C#

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books