find target in tree, delete whole tree if target not found

Question

This is more of a logic problem I'm having a hard time figuring out, I'll post psuedo code, please let me know if anything is unclear.

I'm trying to write a function that will search for multiple instances of a target in an N-array tree (each node has 0 to N children).

If it finds 1 or more instances, it prints them all.
If it finds no instances of the target, the whole tree must be deleted

I'm trying to solve this recursively, this is what I have:

bool foo(node){
    bool found = false
    if node.value = target:
        print target
        return true
    else:
        return false

    for child in node.children:
        found = found or foo(child)
    if not found:
        *run deletion process*
}

The problem with this is the very first if statement:

if node.value = target:
        print target
        return true
    else:
        return false

As soon as it finds the first instance of the target, it returns and stops running. But I want it to find and print ALL instances. But doing this recursively, I'm having a hard time figuring out how to order the code.

Both code paths in your `if` statement return. The code below that is therefore unreachable, and never executes. — Robert Harvey, Jun 28 '15 at 04:31
I understand, this is exactly the problem I'm having. But I *need* those return statements in the `if` block for recursion to work as I see it. — V_TS, Jun 28 '15 at 04:34
How is the code below that ever going to execute if you return from the function before it can execute? — Robert Harvey, Jun 28 '15 at 04:35
I understand this. But I can't do the loop before the base case either. Basically, I'm asking whether recursion is the right technique here. — V_TS, Jun 28 '15 at 04:39
The base case has to return if the base case condition is is fulfilled. If the base condition is not fulfilled, it has to fall through to the recursive case. Have a look at [Fibonnaci](http://stackoverflow.com/questions/8845154/how-does-the-the-fibonacci-recursive-function-work) for a good example of this. — Robert Harvey, Jun 28 '15 at 04:46

Barney · Answer 1 · 2015-06-29T00:59:41.900

As I understand your requirements (delete entire tree if not found), you can't delete the tree from within the recursion. You have to process the entire tree first, then delete it if the target was not found.

So:

bool foo(node){
    bool found = false

    if node.value = target:
        print target
        found = true

    for child in node.children:
        found = found or foo(child)

    return found
}

Then

if not foo(root)
    *run deletion process*

Note that when you actually implement this, some languages will skip the recursive call to foo in found = found or foo(child) once found is true, and so only ever print the first occurrence. In this case, just swap the arguments around: found = foo(child) or found to force it to recurse each time.

find target in tree, delete whole tree if target not found

1 Answers1