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