CODEWITHSUNDEEP
java
GeneralPringles
GeneralPringles

Reputation: 21

comparing two binary tree

Basically this following code will check whether two different binary trees have the same members of integer. The way that I'm supposed to do it is to store the integer from tree to array and then compare the array.

Here is the code that put the integers to array

private static int toarray (btNode t, int[] a, int i)
{
    int num_nodes = 0;
    if (t != null)
    {
        num_nodes = toarray (t.left , a , i);
        a [num_nodes + i] = t.info;
        num_nodes = num_nodes + i + toarray (t.right,a,num_nodes + i + 1);
    }
    return num_nodes;
}

Here is the code that check if the two trees are equal or not

public boolean equals(Intcoll6 obj)
{
    boolean result = true;
    if (how_many == obj.how_many)
    {
        int[]a = new int [how_many];
        int[]b = new int [obj.how_many];


        toarray (c,a,0);
        toarray (obj.c,b,0);


        for (int j = 0; j < how_many; j++)
        {

            if ( a[j] == (b[j]))
            {
                result = true;
            }
            else
                result = false;
        }
   }
   else
   {
        result = false;
   }
    return result;
}

so far (for obvious reason) it only works if the length of tree are not equal. I can't really figure out what's wrong with the code, so any suggestions will help. Thanks in advance

Upvotes: 2

Views: 2314

Answers (3)

Nrj
Nrj

Reputation: 6831

Try using Arrays.deepEquals(a1, a2) for the array comparison. It should work.

You will however need to create an Integer array instead of int since this function works on Object[].

Upvotes: 0

Geeber
Geeber

Reputation: 61

You need to break out of the for loop if you encounter an a[j] != b[j]. Otherwise result will get set to false, but then potentially get set back to true on the next element.

For example, suppose you're comparing the arrays [1,2,3,4,5] and [1,2,-7,4,5]. The first two iterations through the loop will set result = true; the third will set result = false; then the fourth and fifth will again set result = true. By the time you return, you will have result = true, which is wrong.

Perhaps a better approach would be to remove the result = true statement entirely, as it's redundant: you've already initialized result to true. Instead you could just have:

if ( a[j] != (b[j]))
{
    result = false;
    break;
}

Upvotes: 1

Hemant Metalia
Hemant Metalia

Reputation: 30648

Hi you can use the recursion for comparing two binaryTrees the concept may like follow

 int compareTree(tree1, tree2) {
    //if both are empty the return true
 if (tree1==NULL && tree2==NULL) return(true);

// if both non-empty then compare them
else if (tree1!=NULL && tree2!=NULL) {
 return
  //compare values and recursive call the function for next data &&
  //compareTree(left node of tree1,left node of tree2) &&
  //compareTree(right node of tree1,right node of tree2)
  ;
}
// if one empty, and other not then return false
 else return(false);
}

Upvotes: 4

Related Questions