CareerCup

bool IsSum (root, sum) {
if(sum == 0)
return true;

else if (root == null)
return false;

else
return (IsSum(root->left, sum - root->val) ||
IsSum(root->right, sum - root->val) )
}

@msankith

yeah ... you are right ..

I guess this will do ..

bool IsSum (root, sum) {
if(root == null)
return;

if ((sum == root->val) && (root->left == null) && (root->right == null)) //reached root and sum is found
return true;

else if ((root->left == null) && (root->right == null)) // reached leaf node but sum not found
return false;

else
return (IsSum(root->left, sum - root->val) ||
IsSum(root->right, sum - root->val) )
}

Are there some more constraints, say on the values?

How about this ?

/* check if leaf node exists and sum from root to given leaf node = given sum */
	public boolean checkLeafExistsAndSumFromRootIsGivenSum (Object k, int checkSum) throws NoRootException {
		
		/* check if root is present */
		if(getRoot()==null) throw new NoRootException();
		
		/* boolean present to return */
		boolean isPresent = false;
		
		/*sum to sum all items */
		int sum=0;
		
		/*node to store root */
		BinarySearchTreeNodeList node = getRoot();
		
 		/* loop untill null is reached */
		while(node!=null){
			
			/* compare item with object to search */
			int c = (((Comparable)k).compareTo(node.getItem()));
			
			/* if k > node.item */
			if(c>0){
/* if node.right exists then move right else no node exists; return false and stop */
				if(node.getRight()!=null){
		sum=sum (Integer)node.getItem();					
					node=node.getRight();
					isPresent=true;
				}else{
					isPresent=false;break;
				}
				
			}else if(c<0){ /* if k < node.item */
/* if node.left exists move left else no node exists;return false and stop; */
				if(node.getLeft()!=null){
					sum=sum+(Integer)node.getItem();
 					node=node.getLeft();
					isPresent=true;
				}else{
					isPresent=false;break;
				}
			}else if(c==0){
/* if k==node.item then check if sum== check sum else return false and stop; */
				sum=sum+(Integer)node.getItem();
  				if(sum==checkSum)
					isPresent=true;
				else isPresent=false;
				break;
				 
			}
		}
		return isPresent;	
	}

bool isPathExists(node *node,int sum)
{
if(node == null)
return false;
sum = sum - node->value;
if(sum == 0)
return true;
else
if(sum < 0 )
return false;

return (isPathExists(node->left,sum) || isPathExists(node->right,sum))

}

D(n, k)
	if(k == 0 && n == NULL)
		return true
	if(k!=0 && n == NULL)
		return false
	if(k < 0)
		return false
	return D(n->l, k - n->l->d) ||	D(n->r, k - n->r->d)

Elegantly done using DP:
maintain OPT( node, k ) for each node such that OPT( node, k ) = true if some path starting from this node has the sum k. compute from Bottom up from leaf upwards
i.e. OPT( node, k ) = true if OPT( node->left, k - node->value ) = true || OPT( node->right, k - node->value ) = true. O(nk)