Print the path of minimum sum in a binary tree

#include <stdio.h>
#include <stdlib.h>

/*Data structures*/
typedef struct TreeNode
{
struct TreeNode *left, *right;
int data;

}TreeNode;


typedef TreeNode * Tree;


/*End of data structures*/



/*
Two passes with constant space
*/
int minSum(Tree t, int toPrint)
{
if(t == NULL)
return 0;

int lsum = minSum(t->left, 0);
int rsum = minSum(t->right, 0);

if(toPrint)
printf("%d ", t->data);

int sum = t->data;

if(lsum <= rsum)
sum += minSum(t->left, toPrint);
else
sum += minSum(t->right, toPrint);

return sum;

}


/*Utilities*/

inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}

int main()
{
/*level 0*/
Tree t = makeTreeNode(3);

/*level 1*/
t->left = makeTreeNode(2);
t->right = makeTreeNode(4);


/*level 2*/
t->left->left = makeTreeNode(2);
t->left->right = makeTreeNode(1);
t->right->left = makeTreeNode(2);
t->right->right = makeTreeNode(1);

/*print sum*/
minSum(t, 1);
printf("\n");


return 0;
}
Advertisements

3 thoughts on “Print the path of minimum sum in a binary tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s