CareerCup

<pre lang="c++" line="1" title="CodeMonkey23490" class="run-this">bool isPathExists(Node *root,int N)
{
if(root==NULL)
return(N==0);
else
return isPathExists(root->left,N-root->data)||isPathExists(root->right,N-root->data);
}</pre><pre title="CodeMonkey23490" input="yes">1
2
10
42
11

</pre>

- Anonymous May 26, 2010 | Flag Reply

This is just DFS where you keep a running sum, and when the sum goes over what you want you return to parent.

- memo May 27, 2010 | Flag Reply

bool isPathExists(Node *root, int N)
{
return tree(root, 0, N);
}
bool tree(Node *root , int sum, int N)
{
if ( root->left == NULL && root->right ==NULL)
{
if ((sum+root->value) == N)
return true;
else
return false;
}
sum = sum + root->value;
if (tree(root->left, sum, N) == true)
return true;
else if (tree(root->right, sum, N) == true)
return true;
else
return false;
}

- bansal.cool May 27, 2010 | Flag Reply

int ispath(struct node *p,int n)
                {
                        if(p==NULL)
                                return 0;
                        else
                        {
                                n=n-p->d;
                                if(p->l==NULL && p->r==NULL&& n==0)
                                        cout<<"\n Path exists ...";
                                else
                                {
                                        ispath(p->l,n);
                                        ispath(p->r,n);
                                }
                        }
                }

- Anonymous May 30, 2010 | Flag Reply

Does the path have to necessarily start at the root node and end at a leaf? In your original example, what if the desired sum was was 9, and there are connected nodes (3, 6) that sum to to that but neither starts at the root.

Also, a path could comprise of just a single node. Is the desired sum was 7, there are three paths that sum up to this value - (1, 2, 4), (2, 5), and (7).

- Mishra.Anurag June 10, 2010 | Flag Reply

public static boolean isPathExists(Node curr_node, int sum, int N)
{
if(curr_node == null)
{
if(sum == N)
{
return true;
}
else
{
return false;
}
}
else
{
sum = sum + curr_node.value;
if(isPathExists(curr_node.left,sum,N))
return true;
else if(isPathExists(curr_node.right,sum,N))
return true;
else
return false;
}
}

call it like this
isPathExists(myBinaryTree.root, 0, path_value);

- shri June 14, 2010 | Flag Reply

If the path does not have to start from the root, we can apply All Pair shortest path algorithm as there exists exactly one path between all the vertices we get the lengths of all the paths....

- Anonymous July 13, 2010 | Flag Reply

{{{ bool isPath (NODE* root,int sum,int N) { if (sum==N) return true; if (sum > N || root == NULL) return false; sum = sum + root->data ; return isPath (root->right,sum,N) || isPath (root->left,sum,N) ; } {{{ - Anonymous February 21, 2011 | Flag Reply