` 1: 10`

` 2: / \`

` 3: 25 7`

` 4: / \`

` 5: 8 2`

10 -> 25

10 -> 7 -> 8

10 -> 7 -> 2

Some programming questions I found on the net, and are useful to know, are how to print all these paths, given a tree in a structure as below, and another one, how to find if one of these paths has a certain given sum. Both are solved using recursion.

To print all the paths recursively, we need the current node, and a way to know what path reaches till that node. Therefore we could write something like this:

1: void printPaths(struct node* node) {

2: struct node* prevPaths[100];

3: int pathLen = 0;

` 4: printPaths(node, prevPaths, pathLen);`

` 5: }`

1: void printPaths(node* head, node** prevPaths, int pathLen) {

2: if (head == 0) { //we have reached the end, print the existing path

3: cout << "path: ";

4: for (int i = 0; i < pathLen; i++)

5: cout << prevPaths[i]->data << " ";

` 6: cout << endl;`

7: return;

8: } //otherwise

9: prevPaths[pathLen] = head; //add the current node to the path

10: pathLen++; //increase the path length

11: if (head->left == 0 && head->right == 0) //if it has no children then call the function one more time to print the paths

` 12: printPaths(head->left, prevPaths, pathLen);`

13: else if (head->left == 0 && head->right != 0) //if it has one child, continue to it

` 14: printPaths(head->right, prevPaths, pathLen);`

15: else if (head->left != 0 && head->right == 0)

` 16: printPaths(head->left, prevPaths, pathLen);`

17: else {

18: printPaths(head->left, prevPaths, pathLen);//if it has both children, search both

` 19: printPaths(head->right, prevPaths, pathLen);`

` 20: }`

1: int hasPathSum(struct node* node, int sum) {

2: if (node == 0) //we reached a dead end

3: if (sum == 0)

4: return 1;

5: else

6: return 0;

7: sum -= node->data; //otherwise continue to each child with the remaining sum

8: return max(hasPathSum(node->left, sum), hasPathSum(node->right, sum));

` 9: }`

## No comments:

## Post a Comment