write an iterative function pathExists which returns true 6. Graph Search (3 poi

Question

write an iterative function pathExists which returns true

6. Graph Search (3 points) Suppose we define a graph node as follows struct for a single node in a graph. info contains the data visited and is 1 othervise * stored in this node. visited is o if the node has not been struct node nt data; int visited typedef struct node node Array of all the nodes in the graph / node ver [NUNNODES) / 2d array representing the adjacency matrix/ int adj ENUMNODES] CNUMNODES! Write an iterative function pathErists which returns true (i.e. 1) if a path exists from the node ver s to the node ver f) and false (i.e., 0) otherwise. You can assume NUMNODES is a global constant (i.e., you can access it from your function). Reminder: ad loi is 1 if there is an edge from the node verlil to the node verb]. A path is a sequence of 1 or more edges. You have access to queues and stacks if want to use them in your implementation. Assume the following: /* Creates a new queue/stack / queue Q getqueue O stack S getStack ( ); Frees queue/stack ./ freequeue() freeStack(S); /* Add element x to queue/stack insert (Q,x); push (S, x); Check if queue/atack are empty */ isEmpty(Q) isEmpty (S) /+ Remove element from queue/stack »/ x remove() r pop(S)

Explanation / Answer

Answer for the given Question:

See the below method will help you solve the given qestion

*

Given a tree and a sum, return true if there is a path from the root

down to a leaf, such that adding up all the values along the path

equals the given sum.

Strategy: subtract the node value from the sum when recurring down,

and check to see if the sum is 0 when you run out of tree.

*/

bool hasPathSum(struct node* node, int sum)

{

  /* return true if we run out of tree and sum==0 */

  if (node == NULL)

  {

     return (sum == 0);

  }

  

  else

  {

    bool ans = 0;

  

    /* otherwise check both subtrees */

    int subSum = sum - node->data;

  

    /* If we reach a leaf node and sum becomes 0 then return true*/

    if ( subSum == 0 && node->left == NULL && node->right == NULL )

      return 1;

  

    if(node->left)

      ans = ans || hasPathSum(node->left, subSum);

    if(node->right)

      ans = ans || hasPathSum(node->right, subSum);

  

    return ans;

  }

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.