MV_81 - 1 year ago 82
C++ Question

# Recursive tree, printing ancestor nodes

this is study material, not homework:

I have the following tree, I need to write an algorithm that finds a given number and returns an integer indicating how many nodes it visited before finding it. It should also print the values of all "ancestor" nodes relative to the node in which the value was found (in no particular order, and it is assumed that the given value is always present)

``````            10
/  \
20    60
/  \
50  30
\
40
``````

If the given value is 40 it should return 4 and print 30, 20, 10 (in any order)

I've written the following solution, and I think it works, but I'm concerned about the print.

``````void foobar (ty_tree *tree, int value, int & count){
if (tree !=null) {
if (tree->value != value) {
count++;
foobar (tree->left, value, count);
foobar (tree->right, value, count);
cout << tree->value;
}
}
}
``````

Good approach ! But to print the ancestors (i.e.parent nodes) you need to know in your recursive function if the value was found in one of the child:

``````bool foobar (ty_tree *tree, int value, int & count) {
if (tree !=nullptr) {  // oops: NULL or nullptr, the latter is better
if (tree->value != value) {
count++;
if (foobar (tree->left, value, count) ||
foobar (tree->right, value, count) ) // if found below
cout << tree->value<<endl;  // print the node, because it's on the path
}
else {
cout << "Found: "<<tree->value<<endl;  // print the value found
return true;     // and inform caller that he can print as well.
}
}
else return false;  // reached a leaf without finding
}
``````

As some doubts were expressed in the comments, here an online demo

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download