Tree searching function does not give expected result Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of Tree searching function does not give expected result without wasting too much if your time.

The question is published on by Tutorial Guruji team.

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.

We are here to answer your question about Tree searching function does not give expected result - If you find the proper solution, please don't forgot to share this with your team members.

Related Posts

Tutorial Guruji