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.