Get Sum of all Leaf Nodes in Binary Tree

Problem Statement:

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

Consider the image below:

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