# tree equivalence

Page 1 of 1

## 5 Replies - 667 Views - Last Post: 09 January 2013 - 05:43 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=306375&amp;s=ac87c02671500f2a81e82dd8c83e8464&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 aya_eltokhy

• New D.I.C Head

Reputation: 1
• Posts: 22
• Joined: 07-November 12

# tree equivalence

Posted 09 January 2013 - 03:00 PM

hi
i have this code which determined if tow trees are equal or not
the code is working in these cases:
1: equals;
8 8
4 20 4 20

2: the roots not equals
8 80
4 20 4 20

and does not worked in this case
8 8
40 20 4 200

what is the error
``` int  bt_equal  (  binarytree  * tree1,   binarytree * tree2)
{    int   res;
if  (  tree1 == NULL &&  tree2 == NULL )
return (  True  ) ;
res = False ;
if (  tree1  ->   data ==  tree2  ->   data  )
{  res = bt_equal  (  tree1->   lchild  ,  tree2  ->   lchild ) ;
if  ( res  == True )
res = bt_equal  (  tree1  ->   rchild  ,  tree2  ->   rchild ) ;
}
return  ( res );
}

```

case one:
tree 1
8 root
4 lchild
20 rchild

tree2
8 root
4 lchild
20 rchild

case 2
tree 1
8 root
4 lchild
20 rchild

tree2
80 root
4 lchild
20 rchild

case 3
tree 1
8 root
40 lchild
20 rchild

tree2
8 root
4 lchild
200 rchild

Is This A Good Question/Topic? 0

## Replies To: tree equivalence

### #2 Skydiver

• Code herder

Reputation: 4822
• Posts: 15,946
• Joined: 05-May 12

## Re: tree equivalence

Posted 09 January 2013 - 03:52 PM

I must be missing it, but the code as posted should correctly return False for case 3:
```            data lchild  rchild
tree1  -> { 8,   child1, child2 }
child1 -> { 40,  NULL,   NULL }
child2 -> { 20,  NULL,   NULL }
tree2  -> { 8,   child3, child4 }
child3 -> { 4,   NULL,   NULL }
child4 -> { 200, NULL,   NULL }

result = bt_equal(tree1, tree2)
res = False
if (8 == 8)
res = bt_equal(child1, child3)
res = False
if (40 != 4)
// skip
return False
res = False
return False
result = False

```

Was This Post Helpful? 1

### #3 aya_eltokhy

• New D.I.C Head

Reputation: 1
• Posts: 22
• Joined: 07-November 12

## Re: tree equivalence

Posted 09 January 2013 - 04:11 PM

thanks for helping

do you have class for tree has all function???
Was This Post Helpful? 0

### #4 mojo666

• D.I.C Addict

Reputation: 397
• Posts: 859
• Joined: 27-June 09

## Re: tree equivalence

Posted 09 January 2013 - 04:20 PM

I also don't see why case 3 is returning the wrong result, but I do see an issue with the code if you are passed two trees with different shapes. For example, your code will crash if we pass a tree with only a left child and a tree with only a right child. You need to add cases for when one of the input nodes is null and the other is not.
Was This Post Helpful? 1

### #5 aya_eltokhy

• New D.I.C Head

Reputation: 1
• Posts: 22
• Joined: 07-November 12

## Re: tree equivalence

Posted 09 January 2013 - 04:33 PM

i think the problem in the insertion part
```void insert(int key)
{ binarytree *p,*q;
if (root==NULL)
{
root=new binarytree;
cout<<root<<"\n";
root->data=key;
root->lchild=NULL;
cout<<"\n"<<root->lchild;
root->rchild=NULL;
cout<<"\n"<<root->rchild;
return;
}

else{
p=root;
while(p!=NULL)
{
q=p;
if(key>p->data)
p=p->rchild;
else
p=p->lchild;

}

p=new binarytree;
p->lchild=NULL;
p->rchild=NULL;
p->data=key;
if(key>q->data)
{ q->rchild=p;
cout<<"\n"<<q->lchild;
}
else
{q->lchild=p;
cout<<"\n"<<q->rchild;
}
}

}

```

Was This Post Helpful? 0

### #6 Skydiver

• Code herder

Reputation: 4822
• Posts: 15,946
• Joined: 05-May 12

## Re: tree equivalence

Posted 09 January 2013 - 05:43 PM

I don't see what the cout's are buying you in your insert() function unless you are also running your code in a debugger and keeping an eye on the pointer values.

BTW, your cout's for left and right child pointers seem to be swapped on lines 33 and 37.

Also, your current insert() will fail to reproduce tree1 in case 3, because tree1 in case 3 has left child greater than the root which breaks your tree rule here left child must be less than the root.

This post has been edited by Skydiver: 09 January 2013 - 05:44 PM

Was This Post Helpful? 0

Page 1 of 1

 .related ul{list-style-type:circle;font-size:12px;font-weight:bold;}.related li{margin-bottom:5px;background-position:left 7px!important;margin-left:-35px;}.related h2{font-size:18px;font-weight:bold;}.related a{color:blue;}