CareerCup

nice and easy ))
here is the code:

min_so_far = +infty
// two node stacks holding the current path and
// the min sum path found so far
stack< node > cur_path, min_path;

void min_sum(node *t, int sum) {
    cur_path.push(t);
    sum += t->val;
    if(t->left != 0)
        min_sum(t->left, sum);
    else if(t->right != 0)
        min_sum(t->right, sum);
    else { // we are in the leaf node: check the sum
        if(min_so_far > sum) {
            min_so_far = sum;
            min_path = cur_path;
        }
    }
    cur_path.pop(t);    
}

call min_sum(root, 0);

ok just see this every time decision involved weather u have to go left or right so just first check the minimum sum from t->left as root and t->right as a root which is less go there code for this algo
void PrintMinPath(struct node *T)
{
int ls,rs;
if(!T)
return;
printf("%d\n",T->info);
ls=GetMinSum(T->left);
rs=GetMinSum(T->right);
if(ls<=rs)
PrintMinPath(T->left);

else
PrintMinPath(T->right);
}

int GetMinSum(struct node *T)
{
int ls,rs;
if(!T)
return 0;
ls=GetMinSum(T->left)+T->info;
rs=GetMinSum(T->right)+T->info;
if(ls<=rs)
return ls;
else
return rs;
}

Sure but you're calling GetMinSum potentially many times for each node. How about, 2 extensible arrays that are the depth of the tree (or stacks), and a globally least/greatest path sum, and one of the stacks for the best path so far.

Traverse the tree, keeping the sum-so-far on the way down at each node, and pushing the current node into the temporary stack, as you go (pop it on the way back up of course). At the leaf nodes, see whether the sum-so-far is greater / less than the global one, and if so copy the temporary stack to the global one.

At the end, print the global stack.

C(a, b, k)
	for each i from 0 to k-1
		b[i] = a[i]
		
MP(n, s, k)
	if(n->l == NULL && n->r == NULL)
		if(s < sum)
			sum = s
			C(a, b, k)
		return
	a[k+1] = n->l->d	
	MP(n->l, s+n->l->d, k+1)	
	a[k+1] = n->r->d
	MP(n->r, s+n->r->d, k+1)

int maxLen = 0;
node* targetLeaf;

list<char> crt, final;

void findMAXPath(node* root, int length)
{
	if(!root->lchild && !root->rchild)
	{
		if(length + root->element > maxLen)
		{
			targetLef = root;
			maxLen = length + root->element;
			final = crt;
			return;
		}
	}	
	if(!root->lchild)
	{
		crt.pushback('L');
		findMaxPath(root->lchild, length + root->elem);	
	}
	
	if(!root->rchild)
	{
		crt.pushback('R');
		findMaxPath(root->rchild, length + root->elem);
	}

	crt.popback();

	return;		
}