CareerCup

Using Depth First Search (DFS) with two parameters traverse(node, sum). When node = leaf check whether sum equal to given sum (SUM). Along the path whenever the sum exceeds SUM stop that branching.

The total running time is O(V+E) and space is O(V).

Using Depth First Search (DFS) with two parameters traverse(node, sum). When node = leaf check whether sum equal to given sum (SUM). Along the path whenever the sum exceeds SUM stop that branching.

The total running time is O(V+E) and space is O(V).

Pretty easy. DFS. BTW,it's not BST. so should not stop.

yes..shouldnt stop..subsequent nodes could have negative values

can somebody post the code please?

can someone please validate this:

f(node, accumulated_sum, test_val){
     if(node->left==null && node->right==null)
                return node->val+accumulated_sum==test_val

     return f(node->left, node->val+accumulated_sum, test_val) || f(node->right,accumulated_sum,test_val)
}

corrected version:

f(node, accumulated_sum, test_val){
     if(node->left==null && node->right==null)
                return node->val+accumulated_sum==test_val
     return f(node->left, node->val+accumulated_sum, test_val) || f(node->right,node->val+accumulated_sum,test_val)
}

above code look fine

bool HasPathSum(TreeNode root, int sum)
{
 return (NULL == root)?(0 == sum): ( (sum > root->info) && ( HasPathSum(root->left, sum-root->info) || HasPathSum(root->right, sum-root->info) ) );
}

bool HasPathSum(TreeNode root, int sum)
{
 return (NULL == root)?
  (0 == sum):
   ( (sum > root->info) &&
     (  HasPathSum(root->left, sum-root->info) ||
        HasPathSum(root->right, sum-root->info)
     )
   );
}

@ankush I believe you have to add the value at each node , you are just comparing the if "sum > value" at each node

use the characteristic that the IN-ODER TRAVERSAL result of a BST is ASCENDING. then it's straitforward........

int tree(node ptr,int &num)
{static sum=0;
if(ptr==NULL)
{ if(sum==num)
{return 1;}
else
return 0;
}
sum+=ptr->val;
if(tree(ptr->left,num))
{return 1;}
else if(tree(ptr->right,num))
{return 1;}
else
{sum-=ptr->val;
return 0;}
}