In order Traversal Breaking Out Of Recursive Loop

Question

I've search around SOF for a while and read similar post. I didn't find any of those answers satisfactory. The issue i'm having is that I want to traverse a tree until 'the root node' and a target node are the same. If the 'root' == target, I want to return true else false.

This is what I have

private boolean modifiedInorderTraversal(Node newRoot, Node target){     
        if(newRoot.leftPointer != null){
            modifiedInorderTraversal(newRoot.leftPointer, target);
        }

        if(newRoot == target){
            System.out.println("newRoot == target");
            return true;
            //return false;
        } 

        if(newRoot.rightPointer != null){
            modifiedInorderTraversal(newRoot.rightPointer, target);
        }

        System.out.println("before false return");
    //return true;   
        return false; 
    }

You'll notice commented out are return false and return true. I was able to get the program to function properly for all test cases if I swap the returns. However, I personally don't like that solution. I added print statements to trace what issue and I'm using Netbeans as my debugger. When I run the code, it does show that it is entering

if(newRoot == target){
    System.out.println("newRoot == target");
    return true;
    //return false;
} 

I know this because my line is printed. Now, it would seem that my recursion continues despite hitting the return statement true, resulting in the false return of false. I've tried using a global variable to stop the recursion to no avail. Example of that attempt

private breakRecursion = false;

private boolean example(Node newRoot, Node target){
    if(!breakRecursion){
        if(blah blah){recurse}
        if(newRoot == target){breakRecursion = true, return true}
        if(blah blah){recurse}
        return false;
    }
}

Any ideas? I've read that one can use an exception the break the loop, but I thought that was messy too.
***********************UPDATE********************* I found that this works the way I expect it to

private boolean found = false;
    private boolean modifiedInorderTraversal(Node newRoot, Node target){     
        if(newRoot.leftPointer != null){
            modifiedInorderTraversal(newRoot.leftPointer, target);
        }

        if(newRoot == target){
            found = true;
        } 

        if(newRoot.rightPointer != null){
            modifiedInorderTraversal(newRoot.rightPointer, target);
        }

        return found; 
    }

The only issue I have with this solution is that is the runtime is O(n). The worse case should be O(n), but this solution doesn't break early and traverses all the nodes regardless if where the target is found.

Answer 1

Your problem is that when you return from one level in the recursive stack indicating that you found the target, you forget to use this information at the higher levels to stop the search. Try this (remove the print statements in your final product of course):

private static boolean modifiedInorderTraversal(Node newRoot, Node target){     
    boolean foundIt = false;

    if(newRoot.leftPointer != null){
        foundIt = modifiedInorderTraversal(newRoot.leftPointer, target);
        if(foundIt){
            System.out.println("Target found in left subtree");
            return true;
        }
    }

    System.out.println("searching: "+newRoot.value);
    if(newRoot == target){
        System.out.println("Target found at current node!");
        return true; //the target is this node!
    } 

    if(newRoot.rightPointer != null){
        foundIt = modifiedInorderTraversal(newRoot.rightPointer, target);
        if(foundIt){
            System.out.println("Target found in right subtree!");
            return true;
        }
    }

    System.out.println("Not found below root "+newRoot.value);
    return false; //the target is in neither subtree, and is not the root :-(
}

//My tree:
//      a
//    /   \
//    b    c
//   /\    /\
//  d e   f  g
public static void main(String[] arg){
    Node d = new Node(null,null,"d");
    Node e = new Node(null,null,"e");
    Node f = new Node(null,null,"f");
    Node g = new Node(null,null,"g");

    Node b = new Node(d,e,"b");
    Node c = new Node(f,g,"c");

    Node a = new Node(b,c,"a");

    System.out.println("Searching for f");
    if(modifiedInorderTraversal(a, f)){
        System.out.println("Success!");
    }

    System.out.println("---------------------------------");

    System.out.println("Searching for q");
    Node q = new Node(null,null,"q");
    if(modifiedInorderTraversal(a, q)){
        System.out.println("Shouldn't make it here...");
    } else{
        System.out.println("Didn't find q, as we shouldn't");
    }
}

private static class Node {
    public Node(Node left, Node right, String value){
        leftPointer = left;
        rightPointer = right;
        this.value = value;
    }
    Node leftPointer;
    Node rightPointer;
    String value;
}

That will stop the search if the value was found in the left subtree, at the current node, or in the right subtree. If the target isn't found in any one of those, then we give up. Running the above gives:

Searching for f
searching: d
Not found below root d
searching: b
searching: e
Not found below root e
Not found below root b
searching: a
searching: f
Target found at current node!
Target found in left subtree
Target found in right subtree!
Success!
---------------------------------
Searching for q
searching: d
Not found below root d
searching: b
searching: e
Not found below root e
Not found below root b
searching: a
searching: f
Not found below root f
searching: c
searching: g
Not found below root g
Not found below root c
Not found below root a
Didn't find q, as we shouldn't