#### Tree

Problem
Print the sum of all values in the ancestral nodes of a given node in a Binary Tree.
Following figure shows a Binary Tree and the another tree with node values replaced by the ancestral sum. For e.g, for the node 1 , sum of the values of ancestral nodes is 1 + 3 + 7 = 11 and for the node 4 , sum of ancestral nodes is 4 + 5 + 3 + 7 = 19 .

Solution
This problem can be solved by a minor extension of any of the traversal mechanism. We can do an inorder traversal of the tree and maintain the sum of the ancestral node values. See the implementation below.

```#include<iostream>
using namespace std;

typedef struct tree_node {
int value;
struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
node *new_node = new node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

// create the tree
node *createTree() {
node *root = getNewNode(7);
root->left = getNewNode(3);
root->right = getNewNode(11);
root->left->left = getNewNode(1);
root->left->right = getNewNode(5);
root->left->right->left = getNewNode(4);
root->left->right->right = getNewNode(6);
return root;
}

// Inorder traversal of a tree
void inorderTraversal(node *ptr) {
if(ptr == NULL)
return;
else {
inorderTraversal(ptr->left);
cout<<ptr->value<<"\t";
inorderTraversal(ptr->right);
}
}

// Print the sum of all values in the ancestral nodes of a given node
void ancestralSums(node *root,int sum) {
if (!root) return;
sum += root->value;
ancestralSums(root->left,sum);
cout<<sum<<"\t";
ancestralSums(root->right,sum);
}

// main
int main() {
node *root = createTree();
cout<<"\nInorder traversal ...\n\n";
inorderTraversal(root);
cout<<"\n\nAncestral Sum :-\n\n";
ancestralSums(root,0);
cout<<endl;
return 0;
}```