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.

find maximum path sum in binary tree

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



Related Contents to follow