CareerCup

bool checksum(struct node* root, int sum){
        if(root == NULL){
                return (sum == 0);
        }
        int rem = sum-(root->data);

        if(rem == 0)
                return true;
        return (checksum(root->left,sum) || checksum(root->right,sum) || checksum(root->left,rem) ||checksum(root->right,rem));
}

public bool SumExistsOverAnyPathInBinTree(Tree t, int sum)
{
// check (sum - data) is zero
// recurse for the existing tree
// recurse for left subtree and right subtree

if (t == null)
{
return (sum == 0);
}

int data = t.Data;
int result = sum - data;
if (result == 0)
return true;

//need to check for the main tree for the result value
// as well as for left and right subtree for the give sum
return (SumExistsOverAnyPathInBinTree(t, result) ||
SumExistsOverAnyPathInBinTree(t.LeftChild, sum) ||
SumExistsOverAnyPathInBinTree(t.RightChild, sum));

}

func(int sum, node*p)
{
if(sum==given)
{
return true;
}
else if(sum<given)
{
sum+=p->data;
if(p->left!=null)
func(sum,p->left);
if(p->right!-null)
func(sum,p->right);
}
}

boolean pathSum(rooot, sum){

if(root.left==null && root.right){
return sum==0
}else{
int subSum = sum-root.data;
pathSum(root.left,subSum) || pathSum(root.right,subSum)

}
}

bool isSumExistInAnyPath(int sumLeft, NODEPTR root)
{
NODEPTR curr = root;
if (sumLeft - curr->data == 0)
return true;
if (curr->left == NULL && curr->right == NULL)
{
return false;
}
else if (curr->left == NULL && curr->right != NULL)
{
return isSumExistInAnyPath(sumLeft - curr->data, curr->right);
}
else if (curr->right == NULL && curr->left != NULL)
{
return isSumExistInAnyPath(sumLeft - curr->data, curr->left);
}
else
{
if (isSumExistInAnyPath(sumLeft - curr->data, curr->left))
return true;
if (isSumExistInAnyPath(sumLeft - curr->data, curr->right))
return true;
}
return false;
}

what is the meaning of any path
is it path to every leaf node in the tree??

//To check if given sum exists over some path in a tree
int checksum(Node root, int sum){
    if(root==NULL)
        return 0;
    sum-=root->data;
    if((root->left==NULL)&&(root->right==NULL)){
        if(sum==0)
            return 1;
        else
            return 0;
    }
    return (checksum(root->left,sum)||(checksum(root->right,sum)));
}

public boolean sumTraverse(int N, TreeNode root){
		if(root!=null && N - root.data == 0){
			return true;
		} else if(root.leftChild == null && root.rightChild == null){
			return false;
		}
		
		if(sumTraverse(N - root.data, root.leftChild)) return true;
		else if(sumTraverse(N - root.data, root.rightChild)) return true;
		
		return false;
	}

Let say I have a tree as
2
/ \
4 5
/\ /\
1367

Is 4-2-5 also a path?
If yes, then we need to consider all such path

int hasPathSum(struct node *node , int sum){
if(node == NULL)
return (0);

else {
sum-=(node->data);
if(node->left == NULL && node->right == NULL && sum == 0){
return (1);
}
else{
return(max(hasPathSum(node->left,sum),hasPathSum(node->left,sum)));
}
}
}

int hasPathSum(struct node *node , int sum){
if(node == NULL)
return (0);

else {
sum-=(node->data);
if(node->left == NULL && node->right == NULL && sum == 0){
return (1);
}
else{
return(max(hasPathSum(node->left,sum),hasPathSum(node->right,sum)));
}
}
}

int hasPathSum(struct node *node , int sum){
if(node == NULL)
return (0);

else {
sum-=(node->data);
if(node->left == NULL && node->right == NULL && sum == 0){
return (1);
}
else{
return(max(hasPathSum(node->left,sum),hasPathSum(node->left,sum)));
}
}
}

bool btree::hasSum(node* temp, int s)
{
     //same as hasPathSum function
    if (s==0)
        return true;
    else if (temp != NULL && s>=0)
        return (hasSum(temp->left, s-temp->value) || hasSum(temp->right,s-temp->value));
    else
        return false;
}

#include <iostream>
using namespace std;

struct TreeNode
{
	int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
void findIfPathSumToNumber(TreeNode *root, int expectSum, int currentSum,bool &result)
{
	if(!root)
		return;
	bool isLeaf = (root->left == NULL && root->right == NULL);
	currentSum += root->data;
	if(currentSum == expectSum && isLeaf)
		result = true;
	if(root->left)
		findIfPathSumToNumber(root->left, expectSum, currentSum, result);
	if(root->right)
		findIfPathSumToNumber(root->right, expectSum, currentSum, result);
	currentSum -= root->data;
}

bool findIfPathSumToNumber(TreeNode *root, int expectNum)
{
	bool result = false;
	findIfPathSumToNumber(root, expectNum, 0, result);
	return result;
}

int main()
{
	TreeNode *root = new TreeNode(2);
	root->left = new TreeNode(3);
	root->right = new TreeNode(4);
	root->left->left = new TreeNode(5);
	root->left->right = new TreeNode(8);
	root->right->left = new TreeNode(7);
	root->right->right = new TreeNode(9);
	cout<<findIfPathSumToNumber(root, 10);
}