ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Get Sum of all Leaf Nodes in Binary Tree

prodevelopertutorial October 8, 2020

Problem Statement:

Given a binary tree root node, you need to find the sum of all the leaf nodes.

Consider the image below:

binary_tree

The leaf nodes are 7, 15, 18, 30. So the sum is 70.

We can solve this problem by checking if the node is a leaf node or not.

If it is not a leaf node, then we traverse left or right and get to the leaf node and add the value.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};



void get_leaf_sum(Node *node, int &leaf_sum ) 
{
    if (node == NULL) 
    {
      return;
    }

    if ((node->left == NULL) && (node->right == NULL))
    {
        leaf_sum += node->data; 
    }
  
    get_leaf_sum(node->left, leaf_sum); 
    get_leaf_sum(node->right, leaf_sum); 
}


int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);
    
    int leaf_sum = 0;
    get_leaf_sum(root, leaf_sum);

    cout<<"The sum of all leaf nodes are "<<leaf_sum<<endl;

    return 0;  
}

Output:

The sum of all leaf nodes are 70

 

 

 

Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com