Tree searching function does not give expected result

Question

I would like to know why I get the same result with methods containsData and containsData2 in this code.

package rr.fe.op.lab.proc;

class TreeNode {
    TreeNode left;
    TreeNode right;
    String data;
}

class TreeProgram {
    public static void main(String[] args) {
        TreeNode node = null;
        node = insert(node, "Han");
        node = insert(node, "Luke");
        node = insert(node, "Leia");
        node = insert(node, "Padme");
        node = insert(node, "Vader");
        node = insert(node, "Yoda");

        System.out.println("Writing tree inorder:");
        writeTree(node);

        node = reverseTreeOrder(node);
        System.out.println("Writing reversed tree inorder:");

        writeTree(node);
        int size = sizeOfTree(node);
        System.out.println("Number of nodes in tree is "+size+".");

        boolean found = containsData(node, "Padme");
        System.out.println("Searched element is found: "+found);

        boolean found1 = containsData2(node, "Padme");
        System.out.println("Searched element is found: "+found);
    }

    static boolean containsData(TreeNode treeRoot, String data) {
        if(treeRoot == null)
            return false;
        else if(data.compareTo(treeRoot.data) == 0)
        return true;
        else if(data.compareTo(treeRoot.data) < 1)
            return containsData(treeRoot.left,data);
        else 
            return containsData(treeRoot.right,data);
    }

    static int sizeOfTree(TreeNode treeRoot) {
        if(treeRoot == null)
            return 0;
        else 
            return 1 + sizeOfTree(treeRoot.right) + sizeOfTree(treeRoot.left);
    }

    static TreeNode insert(TreeNode treeRoot, String data) {
        if(treeRoot == null){
            TreeNode newnode = new TreeNode();
            newnode.data = data;
            newnode.left = null;
            newnode.right = null;
            return newnode;
        }
        else if (data.compareTo(treeRoot.data) < 1)
            treeRoot.left = insert(treeRoot.left,data);
        else 
            treeRoot.right = insert(treeRoot.right,data);
        return treeRoot;
    }

    static void writeTree(TreeNode treeRoot) {
        if(treeRoot != null){
            writeTree(treeRoot.left);
            System.out.println(treeRoot.data);
            writeTree(treeRoot.right);
        }
    }

    static TreeNode reverseTreeOrder(TreeNode treeRoot) {
        if(treeRoot == null)
            return null;

        TreeNode node = new TreeNode();
        node = treeRoot.left;
        treeRoot.left = treeRoot.right;
        treeRoot.right = node;

        reverseTreeOrder(treeRoot.left);
        reverseTreeOrder(treeRoot.right);
        return treeRoot;
    }

    static boolean containsData2(TreeNode treeRoot,String data){
        if (treeRoot == null) {
            return false;
        }

        if (treeRoot.data == data){
            return true;
        } else {
            return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);
        }

    }  
}

I know that before reversing the tree, the method containsData works fine. When I reverse the tree, it is not working which is ok. I wrote a method containsData2 with idea that that method can find elements whether the tree is reversed or not. Of course, complexity will be higher. But, with containsData2, I get the same result as containsData, namely false. What I am doing wrong?

Did you try to debug it? maybe your `treeRoot` is null. – SomeJavaGuy Oct 16 '15 at 07:43 — SomeJavaGuy, Oct 16 '15 at 07:43

score 2 · Accepted Answer · edited May 23 '17 at 10:27

The main problem is that you put the wrong variable in your print statement:

boolean found1 = containsData2(node, "Padme");
System.out.println("Searched element is found: "+found);

This should be:

boolean found1 = containsData2(node, "Padme");
System.out.println("Searched element is found: "+found1);

Another important problem is that you are trying to compare Strings using ==, which will usually not give the results you want. In this particular case it works, because you are only using literal Strings. The comparison is done here:

if (treeRoot.data == data){
    return true;
} else {
    return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);
}

Instead, compare your Strings using the equals method, like this:

if (treeRoot.data.equals(data)){
    return true;
} else {
    return containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);
}

Or, if you want to simplify the code further:

return treeRoot.data.equals(data) ||
       containsData2(treeRoot.left,data) || containsData2(treeRoot.right,data);

For more information on comparing Strings, see this question.

Nope, In line 'if (treeRoot.data == data)' he is comparing the same objects, so in that particular case it is not the difference if he uses == or equal method. The problem is wrongly understood recursion. But I fully agree with you, that while comparing Strings you should use equals method. — Thamiar, Oct 16 '15 at 08:48
You were right about the String comparison not being the main problem. The recursion is okay though. After some testing I found that there is just a small error in the print statement. Somehow we all overlooked this. ;-) — Thomas, Oct 16 '15 at 09:15

Thamiar · Answer 2 · 2015-10-16T08:21:22.643

You have misunderstood the recursion. What are you doing now is, searching the tree:

Han (he is not Padme, let's dig more) ->
_____Luke (he is not Padme, let's dig more ->
__________Padme (hey, it's her!) return true!
_____Going back to Luke, he is not Padme, so we return false
Going back to Han, he is not Padme, so we return false.

At the end, your get the "False" boolean, "This is not the node you are looking for?"

You should try to find another approach to this problem. At the moment, you should try to break out of recursion, when you will find a proper node. The easiest way is to create a global variable, and set

done = true;

When Padme is found, and then, while printing the result: System.out.println("Searched element is found: "+done);

Tree searching function does not give expected result

2 Answers2