CareerCup

hmm not sure about this,
Do you mean sum of nodes traversed from root to leaf. Does the sum alywas include the root ?

findsum(root,sum){

if(sum<0) return 0;

if(sum==root->value) return -1;

if(root==NULL) return 0;

int num_node=0;

int right=findsum(root->right,sum-root->value);

if(right>0) num_node=right+1; return num_node;

else if(right<0) num_node=1;  return num_node;

int left=findsum(root->left ,sum-root->value);

if(left>0) num_node=left+1;  return num_node;

else if(left<0) num_node=1;  return num_node;

return 0;

@Anonymous .. the required sum and the data values in the nodes can also be negative.you need to take care of that..so going to the right subtree doesn't ensure that we reach the minimum first..

Call
minsum(root, sumToBeFound, 0, 0, MAX_NUMBER);

node *minsum(node *root, int sum,int parentsum, int depth, out int mindepth)
{
	if(null == root || mindepth == depth)
	{
		return null;
	}

	parentsum = parentsum + root->data;
	if(temp == sum)
	{
		minddepth = depth;2
		return root;
	}
	else if(temp > sum)
	{
		return null;
	}

	Node *temp1 = mindsum(root->left, sum, parentsum, depth + 1, minddepth);
 
	Node *temp2 = mindsum(root->right, sum, parentsum, depth + 1, mindepth);
	if(null != temp1)
	{
		return temp1;
	}
	else if(null != temp2)
	{
		return temp2;
	}

	return null;

}

I do agree that changing function arguments is not the good practice but the cases like this where one have to
a) Rely on size
b) Global variable (against the reentrant programming).

Its better to write a private function with desired no of arguments .SO this way we wrap around solution (this funda known as wrapper).

minsum(root,n)=min{1+minsum(root.left,n-root.data),1+minsum(root.right,n-root.data),minsum(root.left,n),minsum(root.right,n)}

fun (node,sum)
{
if(node==null && sum==0)
return true;
else if(node==null) //but sum!=0
return false;
else if(sum < node->key) //sum is less than node--> key so only search area is left side of the node
return fun(left,sum-node->key);
else
return (fun(left,sum - node->key)||fun(right,sum - node->key) //if sum is greater than node-->key then we have to search in both side and then take or of those two result
}

a little correction in above

in third condtion
else if(sum < node -->key)
return false;

above code work only when numbers are +ve

1. Use BFS traversal (use queue)
2. at each node currentSum = sum obtained from parent + current value
3. if the currentSum is the required sum and node is leaf node, you have got solution
4. else if currentSum > required sum, do not add child
5. else
5.a Add left child to the queue;
5.b add right child to queue only if (requiredSum-currentSum<=currentSum)


BFS ensures minimum solution. 5.b and 4 steps prune search space

node* findNodeForSum( node *root, int& sum, const int desiredsum)
{
if( root == null )
{
return null;
}
else
{
sum += root.value;
if( sum == desiredsum &&
//ensure leaf
root->left == null &&
root->right == null )
{
return root;
}
else
{
Node *result = findNodeForSum( root->left, sum, desiredsum );
if( result == null )
{
Node *result = findNodeForSum( root->right, sum, desiredsum );
}
// if we are returning null decrement sum then we should return it to prior state
if( result == null )
sum -= root.value;
return result;
}
}
}

this was coded on the fly but should work.

public treeNode MinimumNodeFromRootHavingSum(treeNode curr, int sum)
{
if (curr == null || sum < 0)
return null;

int subsum = sum - curr.value;

if (subsum == 0)
return curr;

treeNode leftResult = MinimumNodeFromRootHavingSum(curr.leftChild, subsum);
treeNode rightResult = MinimumNodeFromRootHavingSum(curr.rightChild, subsum);

return (leftResult != null)? leftResult :
(rightResult != null)? rightResult : null;

}

geeksforgeeks.org/ ?p=6201