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.