Adobe Interview Question
Java DevelopersCountry: 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