• • Given a binary tree write a c program to find maximum sum from root to leaf in a binary tree. For example if given binary tree is as below In the above binary tree the maximum sum from root to leaf is 19 ( 6->5->8). Let us write  c program and learn how it works.

## c program to find maximum sum from root to leaf in a binary tree

```#include<stdio.h>
#include<malloc.h>

// data structure for binary tree
struct Tree
{
int value;
struct Tree *left;
struct Tree *right;
};

struct Tree *root = NULL;

struct Tree *
makeNewNode (int value)
{
struct Tree *node = (struct Tree *) malloc (sizeof (struct Tree));
node->value = value;
node->left = NULL;
node->right = NULL;

return node;
}

// function to find max sum

int maxSumFromRootToLeaf (struct Tree *root)
{
// base case
if (root == NULL)
return 0;

int l = maxSumFromRootToLeaf (root->left);
int r = maxSumFromRootToLeaf (root->right);

if (l > r)
return l + root->value;
else
return r + root->value;
}

int main ()
{
/*
(6)
/\
/  \
(8)  (5)
/ \
/   \
(8)  (3)

*/

root = makeNewNode (6);
root->left = makeNewNode (8);
root->right = makeNewNode (5);

root->right->left = makeNewNode (8);
root->right->right = makeNewNode (3);

root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right->left = NULL;
root->right->right->right = NULL;

int sum = maxSumFromRootToLeaf (root);
printf ("The max sum from root to leaf is %d \n", sum);

return 0;
}
```

### How it works:

• Traverse the binary tree from bottom up.
• Calculate the max sum from node to leaf for left child.
• Calculate the max sum from node to leaf for right child. Time Complexity : O (n)