## Adobe Interview Question for Java Developers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
3
of 3 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

I think it willl work if all number are positive in the binary tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

I assume, here path means leaf node of the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Can also check if the "sum" variable becomes -ve before reaching root.
Identifying this case will lead to fast termination in case of really long trees.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Oh sorry! I thought two values adding up to the sum

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

why are you using max function .. i think you shud not use it.

Comment hidden because of low score. Click to expand.
0

u can use || also....i just used it bcoz i had a macro for that:P

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

ya sorry.... it should be node->left and node-> right

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.