## Adobe Interview Question

Java Developers**Country:**India

**Interview Type:**Written Test

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);

}

}

func(int sum, node*p)

{

if(sum==given)

{

return true;

}

else if(sum<given)

{

if (sum+p->data < given)

sum+=p->data;

if(p->left!=null)

func(sum,p->left);

if(p->right!-null)

func(sum,p->right);

}

}

Does this search all the paths in the tree? I guess not! Can someone please tell an efficient algorithm for this one? Thanks.

Does this search all the paths in the tree? I guess not! Can someone please tell an efficient algorithm for this one? Thanks.

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;

}

```
//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;
}
```

This wont work because for three values summing up to the value, the function returns true.

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)));

}

}

}

Naveen i think you need to review you code again ...

```
return(max(hasPathSum(node->left,sum),hasPathSum(node->left,sum)));
//is same as ..
return (hasPathSum(node->left,sum);
```

```
#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);
}
```

- Anonymous April 22, 2012