Question:
Given a binary tree root node, get the sum of the values of all the nodes formed from root to the leaf node.
Solution:
From the above image, we have 4 leaf nodes i.e : 3, 4, 6, 7
So the paths will be
1 -> 2 -> 3 Number = 123
1 -> 2 -> 4 Number = 124
1 -> 5 -> 6 Number = 156
1 -> 5 -> 7 Number = 157
So the sum will be:
123 + 124 + 156 + 157 = 560
Solution is to do pre order traversal and keep track of the value calculated till that node.
For every node multiply the value with 10 + node’s data.
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; } }; int value_root_to_leaf; void sum_root_to_leaf(Node *node, int i) { if (node == NULL) { return; } if (node->left == NULL && node->right == NULL) { value_root_to_leaf = value_root_to_leaf + (i * 10 + node->data); return; } sum_root_to_leaf(node->left, i * 10 + node->data); sum_root_to_leaf(node->right, i * 10 + node->data); } int main() { Node* root = nullptr; /* Binary tree: 1 / \ / \ 2 5 / \ / \ / \ / \ 3 4 6 7 */ root = new Node(1); root->left = new Node(2); root->right = new Node(5); root->left->left = new Node(3); root->left->right = new Node(4); root->right->left = new Node(6); root->right->right = new Node(7); sum_root_to_leaf(root, 0); cout<<"The sum of root to leaf is "<<value_root_to_leaf<<endl; return 0; }
Output
The sum of root to leaf is 560