# c program to find maximum path sum in binary tree

Write a c program to find maximum path sum in binary tree. The path may starts at any node and end at any other node in the given binary tree. For example in given below binary tree the maximum path sum is 27 and path is 8->6->5->8.

*c program to find maximum path sum in binary tree*

#include<stdio.h> #include<malloc.h> #include<limits.h> // data structure for binary tree struct Tree { int val; 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->val = value; node->left = NULL; node->right = NULL; return node; } int max(int a, int b) { return a > b ? a : b; } int result = INT_MIN; // function to find max path sum int maxPathSum(struct Tree *root) { // base case if (root == NULL) return 0; int left_max = maxPathSum(root->left); int right_max = maxPathSum(root->right); int mx = max(max(left_max + root->val, right_max + root->val), root->val); result = max(result, max(mx, left_max + root->val + right_max)); return mx; } 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; maxPathSum(root); printf("The max path sum is %d \n", result); return 0; }

Ref:

https://leetcode.com/problems/binary-tree-maximum-path-sum/#/description

## Leave a Reply