#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

we Can use lsum or rsum while adding to sum, right ?You are doing awesome job here samba. -brahma

It would be highly useful to provide a two line summary/desc of the approach and type of algorithm (backtracking, divide&conquer etc.)

Could you please explain the Algo????