MV_81 MV_81 - 9 days ago 5
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;
}
}
}

Answer

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

Comments