Tree searching function does not give expected result

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?

Answer

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.

Leave a Reply

Your email address will not be published. Required fields are marked *