WAP to Find Path of Minimum Sum in Binary Tree Efficiently

Data Structure Used:Binary Tree

Algorithm(Recursion)
For each node use two variable left & right for left & right subtree
find minimum in left & right sub tree & add root value to minimum
this algorithm requires two passes over binary tree with constant spaces.


#include
#include


struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int minSuminBT(struct node* t, int print)
{
if(t == NULL)
return 0;

left=t->left->data;
right=t-right->data;

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

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

int sum = t->data;

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

return sum;

}

/* Driver program to test mirror() */
int main(void)
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(3);
root->left->right = newNode(2);
root->right->left = newNode(1);
root->right->right = newNode(2);

minSuminBT(root,1);//answer 1-2-2
getchar();
return 0;
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/RWbhP