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

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:**

**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)

## Leave a Reply