By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,220 Members | 1,798 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,220 IT Pros & Developers. It's quick & easy.

Trouble with Isomorphism in Trees

Ganon11
Expert 2.5K+
P: 3,652
Hey guys,

OK, taking care of this beforehand; I AM a student in a university. This IS part of my homework, and (as a moderator), I'm doing my best to follow the posting guidelines I work so hard to enforce.

Anyway, I'm trying to implement an areIsomorphic(TreeNode<T> first, TreeNode<T> second) function as defined below:

Two Binary Trees T1 and T2 are isomorphic if one of the following holds.

* Both T1 and T2 consist of a single node.
* Left Subtree of T1 and Left Subtree of T2 are isomorphic and Right Subtree of T1 and Right Subtree of T2 are isomorphic.
* Left Subtree of T1 and Right Subtree of T2 are isomorphic and Right Subtree of T1 and Left Subtree of T2 are isomorphic.

Write C++ code for testing whether two given binary trees are isomorphic and submit the code and results with sample test runs of binary trees.
Since this is a 'simple' problem, I've tried to do it using only TreeNodes rather than writing my own tree class just for this simple function. (And, my fellow experts/moderators, YES, I am being asked to reinvent the wheel, there's no avoiding it). My code is as follows:

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAX_SIZE = 10;
  5.  
  6. template <class T>
  7. struct TreeNode {
  8.     TreeNode<T> *left;
  9.     TreeNode<T> *right;
  10.     T data;
  11. };
  12.  
  13. template <class T>
  14. bool areIsomorphic(TreeNode<T> *first, TreeNode<T> *second);
  15.  
  16. template <class T>
  17. void createTree(TreeNode<T> *node);
  18.  
  19. template <class T>
  20. void insert(TreeNode<T> *node, T obj);
  21.  
  22. template <class T>
  23. void printTree(TreeNode<T> *node);
  24.  
  25. int main() {
  26.     srand((unsigned)time(NULL));
  27.     TreeNode<int> *first, *second;
  28.     createTree(first);
  29.     createTree(second);
  30.     printTree(first);
  31.     cout << endl << endl;
  32.     printTree(second);
  33.     cout << endl << endl;
  34.     if (areIsomorphic(first, second)) {
  35.         cout << "The trees are isomorphic." << endl;
  36.     } else {
  37.         cout << "The trees are not isomorphic." << endl;
  38.     }
  39.     return 0;
  40. }
  41.  
  42. template <class T>
  43. void createTree(TreeNode<T> *node) {
  44.     cout << "Entering createTree..." << endl;
  45.     node = new TreeNode<T>;
  46.     for (int i = 0; i < MAX_SIZE; i++)
  47.         insert(node, rand() % 50);
  48. }
  49.  
  50. template <class T>
  51. void insert(TreeNode<T> *temp, T obj) {
  52.     cout << "Entering insert with obj = " << obj << endl;
  53.     if (temp == NULL) temp->data = obj;
  54.     else {
  55.         if (temp->data < obj) {
  56.             if (temp->right == NULL) {
  57.                 TreeNode<T> *newNode = new TreeNode<T>;
  58.                 newNode->data = obj;
  59.                 temp->right = newNode;
  60.             } else insert(temp->right, obj);
  61.         } else {
  62.             if (temp->left == NULL) {
  63.                 TreeNode<T> *newNode = new TreeNode<T>;
  64.                 newNode->data = obj;
  65.                 temp->left = newNode;
  66.             } else insert(temp->left, obj);
  67.         }
  68.     }
  69. }
  70.  
  71. template <class T>
  72. void printTree(TreeNode<T> *node) {
  73.     cout << "Entering printTree..." << endl;
  74.     if (node != NULL) {
  75.         printTree(node->left);
  76.         cout << " " << node->data;
  77.         printTree(node->right);
  78.     }
  79. }
  80.  
  81. template <class T>
  82. bool areIsomorphic(TreeNode<T> *first, TreeNode<T> *second) {
  83.     cout << "Entering areIsomorphic..." << endl;
  84.     if (first == NULL && second == NULL) return true;
  85.     else if (first == NULL || second == NULL) return false;
  86.     else if (first->left == NULL && second->left == NULL && first->right == NULL && second->right == NULL) return true;
  87.     else if (areIsomorphic(first->left, second->left) && areIsomorphic(first->right, second->right)) return true;
  88.     else if (areIsomorphic(first->left, second->right) && areIsomorphic(first->right, second->left)) return true;
  89.     else return false;
  90. }
  91.  
and I get this as output:

$ ITest
Entering createTree...
Entering insert with obj = 2
Entering insert with obj = 21
Entering insert with obj = 21
Entering insert with obj = 8
Entering insert with obj = 8
Entering insert with obj = 8
Entering insert with obj = 5
Entering insert with obj = 5
Entering insert with obj = 5
Entering insert with obj = 5
Entering insert with obj = 6
Entering insert with obj = 6
Entering insert with obj = 6
Entering insert with obj = 6
Entering insert with obj = 6
Entering insert with obj = 42
Entering insert with obj = 42
Entering insert with obj = 42
Entering insert with obj = 37
Entering insert with obj = 37
Entering insert with obj = 37
Entering insert with obj = 37
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 35
Entering insert with obj = 35
Entering insert with obj = 35
Entering insert with obj = 35
Entering insert with obj = 35
Entering insert with obj = 35
Entering insert with obj = 20
Entering insert with obj = 20
Entering insert with obj = 20
Entering insert with obj = 20
Entering createTree...
Entering insert with obj = 42
Entering insert with obj = 22
Entering insert with obj = 22
Entering insert with obj = 26
Entering insert with obj = 26
Entering insert with obj = 26
Entering insert with obj = 39
Entering insert with obj = 39
Entering insert with obj = 39
Entering insert with obj = 39
Entering insert with obj = 41
Entering insert with obj = 41
Entering insert with obj = 41
Entering insert with obj = 41
Entering insert with obj = 41
Entering insert with obj = 17
Entering insert with obj = 17
Entering insert with obj = 17
Entering insert with obj = 49
Entering insert with obj = 49
Entering insert with obj = 31
Entering insert with obj = 31
Entering insert with obj = 31
Entering insert with obj = 31
Entering insert with obj = 31
Entering insert with obj = 18
Entering insert with obj = 18
Entering insert with obj = 18
Entering insert with obj = 18
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 29
Entering insert with obj = 29
Entering printTree...
Entering printTree...
27494 [main] ITest 7016 _cygtls::handle_exceptions: Error while dumping state
(probably corrupted stack)
Segmentation fault (core dumped)
I'm not sure why I'm getting a seg. fault error, and apparently in the print function, which is the one function I'm almost sure is correct. Is there some glaring error I've made that is messing this up?
Sep 24 '07 #1
Share this Question
Share on Google+
17 Replies


Ganon11
Expert 2.5K+
P: 3,652
Also, does anyone know why I'm getting all these repeat values for my insertions?
Sep 24 '07 #2

ilikepython
Expert 100+
P: 844
Hey guys,

OK, taking care of this beforehand; I AM a student in a university. This IS part of my homework, and (as a moderator), I'm doing my best to follow the posting guidelines I work so hard to enforce.

Anyway, I'm trying to implement an areIsomorphic(TreeNode<T> first, TreeNode<T> second) function as defined below:



Since this is a 'simple' problem, I've tried to do it using only TreeNodes rather than writing my own tree class just for this simple function. (And, my fellow experts/moderators, YES, I am being asked to reinvent the wheel, there's no avoiding it). My code is as follows:

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAX_SIZE = 10;
  5.  
  6. template <class T>
  7. struct TreeNode {
  8.     TreeNode<T> *left;
  9.     TreeNode<T> *right;
  10.     T data;
  11. };
  12.  
  13. template <class T>
  14. bool areIsomorphic(TreeNode<T> *first, TreeNode<T> *second);
  15.  
  16. template <class T>
  17. void createTree(TreeNode<T> *node);
  18.  
  19. template <class T>
  20. void insert(TreeNode<T> *node, T obj);
  21.  
  22. template <class T>
  23. void printTree(TreeNode<T> *node);
  24.  
  25. int main() {
  26.     srand((unsigned)time(NULL));
  27.     TreeNode<int> *first, *second;
  28.     createTree(first);
  29.     createTree(second);
  30.     printTree(first);
  31.     cout << endl << endl;
  32.     printTree(second);
  33.     cout << endl << endl;
  34.     if (areIsomorphic(first, second)) {
  35.         cout << "The trees are isomorphic." << endl;
  36.     } else {
  37.         cout << "The trees are not isomorphic." << endl;
  38.     }
  39.     return 0;
  40. }<snipped otheer wise post woudnt show>
  41.  
and I get this as output:



I'm not sure why I'm getting a seg. fault error, and apparently in the print function, which is the one function I'm almost sure is correct. Is there some glaring error I've made that is messing this up?
I think you should really use a class with constructors and destructors for the nodes and the list. You never free any of your memory. Also, I think your problem is in your insert function. First you check if the pointer is NULL, and if it is you try to use it. I think when you create a new node you should make all of its left and right pointers NULL. I don't have a lot of time, sorry. I'll look at it more later.
Sep 24 '07 #3

Expert 100+
P: 849
For the segfaults, those are when you try to dereference/print a NULL pointer, so you're getting NULLs passed to the printing part of that somehow.
Sep 24 '07 #4

Ganon11
Expert 2.5K+
P: 3,652
Can't believe I made such a stupid mistake...

OK, I've fixed the insert function (and also the createTree function) to look like this:

Expand|Select|Wrap|Line Numbers
  1. template <class T>
  2. void createTree(TreeNode<T> *node) {
  3.     cout << "Entering createTree..." << endl;
  4.     for (int i = 0; i < MAX_SIZE; i++)
  5.         insert(node, rand() % 50);
  6. }
  7.  
  8. template <class T>
  9. void insert(TreeNode<T> *temp, T obj) {
  10.     cout << "Entering insert with obj = " << obj << endl;
  11.     if (temp == NULL) {
  12.         temp = new TreeNode<T>;
  13.         temp->data = obj;
  14.     } else {
  15.         if (temp->data < obj) {
  16.             if (temp->right == NULL) {
  17.                 TreeNode<T> *newNode = new TreeNode<T>;
  18.                 newNode->data = obj;
  19.                 temp->right = newNode;
  20.             } else insert(temp->right, obj);
  21.         } else {
  22.             if (temp->left == NULL) {
  23.                 TreeNode<T> *newNode = new TreeNode<T>;
  24.                 newNode->data = obj;
  25.                 temp->left = newNode;
  26.             } else insert(temp->left, obj);
  27.         }
  28.     }
  29. }
So, in this case, if temp is NULL, I make a new TreeNode and THEN use it. However, this now compiles and runs, showing 2 insertions being made before the same type of error:

Entering createTree...
Entering insert with obj = 20
Entering insert with obj = 20
29 [main] ITest 5928 _cygtls::handle_exceptions: Error while dumping state
(probably corrupted stack)
Segmentation fault (core dumped)
EDIT: I have also, at the behest of my roommate, added a deconstructor for the TreeNode struct:

Expand|Select|Wrap|Line Numbers
  1. template <class T>
  2. TreeNode<T>::~TreeNode() {
  3.     delete left;
  4.     delete right;
  5. }
Sep 24 '07 #5

RRick
Expert 100+
P: 463
You've got a problem with createTree. You create a nice tree, but you never return the pointer value from inside that routine. You pass the pointer in, and set the pointer value, but it never gets back to the calling routine.

You can pass a ** or a *& to createTree and that will fix that problem.
Sep 25 '07 #6

Ganon11
Expert 2.5K+
P: 3,652
You've got a problem with createTree. You create a nice tree, but you never return the pointer value from inside that routine. You pass the pointer in, and set the pointer value, but it never gets back to the calling routine.

You can pass a ** or a *& to createTree and that will fix that problem.
Good advice - advice I hadn't thought of - so I changed the function to this:

Expand|Select|Wrap|Line Numbers
  1. template <class T>
  2. void createTree(TreeNode<T> **node) {
  3.     cout << "Entering createTree..." << endl;
  4.     for (int i = 0; i < MAX_SIZE; i++)
  5.         insert(*node, rand() % 50);
  6. }
and I'm now calling it with createTree(&first). Same errors.
Sep 25 '07 #7

ilikepython
Expert 100+
P: 844
Can't believe I made such a stupid mistake...

OK, I've fixed the insert function (and also the createTree function) to look like this:

Expand|Select|Wrap|Line Numbers
  1. template <class T>
  2. void createTree(TreeNode<T> *node) {
  3.     cout << "Entering createTree..." << endl;
  4.     for (int i = 0; i < MAX_SIZE; i++)
  5.         insert(node, rand() % 50);
  6. }
  7.  
  8. template <class T>
  9. void insert(TreeNode<T> *temp, T obj) {
  10.     cout << "Entering insert with obj = " << obj << endl;
  11.     if (temp == NULL) {
  12.         temp = new TreeNode<T>;
  13.         temp->data = obj;
  14.     } else {
  15.         if (temp->data < obj) {
  16.             if (temp->right == NULL) {
  17.                 TreeNode<T> *newNode = new TreeNode<T>;
  18.                 newNode->data = obj;
  19.                 temp->right = newNode;
  20.             } else insert(temp->right, obj);
  21.         } else {
  22.             if (temp->left == NULL) {
  23.                 TreeNode<T> *newNode = new TreeNode<T>;
  24.                 newNode->data = obj;
  25.                 temp->left = newNode;
  26.             } else insert(temp->left, obj);
  27.         }
  28.     }
  29. }
So, in this case, if temp is NULL, I make a new TreeNode and THEN use it. However, this now compiles and runs, showing 2 insertions being made before the same type of error:



EDIT: I have also, at the behest of my roommate, added a deconstructor for the TreeNode struct:

Expand|Select|Wrap|Line Numbers
  1. template <class T>
  2. TreeNode<T>::~TreeNode() {
  3.     delete left;
  4.     delete right;
  5. }
I don't know if this is going to fix your problem, but I think you don't need all of that code in the insert():
Expand|Select|Wrap|Line Numbers
  1. template <class T>
  2. void insert(TreeNode<T> *temp, T obj) {
  3.     cout << "Entering insert with obj = " << obj << endl;
  4.     if (temp == NULL) {
  5.         temp = new TreeNode<T>;
  6.         temp->data = obj; } 
  7.  
  8.     else {
  9.         if (temp->data < obj) {
  10.             insert(temp->right, obj); }    // go right to insert since you handle if pointer is NULL at the top of the function
  11.  
  12.         else {
  13.          insert(temp->left, obj); }
  14.         }
  15.     }
  16.  
Sep 25 '07 #8

Ganon11
Expert 2.5K+
P: 3,652
Will that work? If, for instance, obj is greater than the node we have, then we use insert(node->right, obj). Let's say this is NULL. Then node->right is pointing to nonsense - yet I turn that memory location into a TreeNode. Shouldn't I have to change the previous TreeNode's right to point to the new TreeNode?
Sep 25 '07 #9

Ganon11
Expert 2.5K+
P: 3,652
OK, I figured out the problem has to be in my createTree and insert functions. Here is what they are as of today:

Expand|Select|Wrap|Line Numbers
  1. void createTree(TreeNode<int> **node) {
  2.     cout << "Entering createTree..." << endl;
  3.     (*node) = new TreeNode<int>;
  4.     (*node)->data = rand() % 50;
  5.     for (int i = 1; i < MAX_SIZE; i++)
  6.         insert(*node, rand() % 50);
  7. }
  8.  
  9. void insert(TreeNode<int> *temp, int obj) {
  10.     cout << "Entering insert with obj = " << obj << endl;
  11.     if (temp == NULL) {
  12.         temp = new TreeNode<int>;
  13.         temp->data = obj;
  14.     } else {
  15.         cout << "temp->data = " << temp->data << endl;
  16.         if (temp->data < obj)
  17.             insert(temp->right, obj);
  18.         else if (obj < temp->data)
  19.             insert(temp->left, obj);
  20.         else
  21.             ;
  22.     }
  23. }
Now, I'm looking in my book (Data Structures and Algorithm Analysis in C++, Mark Allen Weiss), and the insert function is pretty much letter-for-letter copied. But my 'debugging' cout statements indicate that neither tree ever grows - they always consist only of the original int given to the root.

This is due Thursday...really appreciate everyone's help so far.
Sep 25 '07 #10

Savage
Expert 100+
P: 1,764
OK, I figured out the problem has to be in my createTree and insert functions. Here is what they are as of today:

Expand|Select|Wrap|Line Numbers
  1. void createTree(TreeNode<int> **node) {
  2.     cout << "Entering createTree..." << endl;
  3.     (*node) = new TreeNode<int>;
  4.     (*node)->data = rand() % 50;
  5.     for (int i = 1; i < MAX_SIZE; i++)
  6.         insert(*node, rand() % 50);
  7. }
  8.  
  9. void insert(TreeNode<int> *temp, int obj) {
  10.     cout << "Entering insert with obj = " << obj << endl;
  11.     if (temp == NULL) {
  12.         temp = new TreeNode<int>;
  13.         temp->data = obj;
  14.     } else {
  15.         cout << "temp->data = " << temp->data << endl;
  16.         if (temp->data < obj)
  17.             insert(temp->right, obj);
  18.         else if (obj < temp->data)
  19.             insert(temp->left, obj);
  20.         else
  21.             ;
  22.     }
  23. }
Now, I'm looking in my book (Data Structures and Algorithm Analysis in C++, Mark Allen Weiss), and the insert function is pretty much letter-for-letter copied. But my 'debugging' cout statements indicate that neither tree ever grows - they always consist only of the original int given to the root.

This is due Thursday...really appreciate everyone's help so far.

I think that your problem is in create function.You need to initialize in it left and right to NULL.

I tried it with VC 2005.NET with this added and it worked perfectly.

Savage
Sep 25 '07 #11

Savage
Expert 100+
P: 1,764
I think that your problem is in create function.You need to initialize in it left and right to NULL.

I tried it with VC 2005.NET with this added and it worked perfectly.

Savage
Oops just discovered something intriguing:try printing data and obj and see if they match.

Savage
Sep 25 '07 #12

Savage
Expert 100+
P: 1,764
Oops just discovered something intriguing:try printing data and obj and see if they match.

Savage
Try making your insert function take a double pointer,because you perform allocation inside it.


Savage
Sep 25 '07 #13

Ganon11
Expert 2.5K+
P: 3,652
After making just about everything double pointers, the program finally worked! Thanks a lot, guys.

Now, do you think you can give me a hand implementing a set using a Binary Search Tree? I think I'll start a new thread for that one.
Sep 25 '07 #14

Savage
Expert 100+
P: 1,764
After making just about everything double pointers, the program finally worked! Thanks a lot, guys.

Now, do you think you can give me a hand implementing a set using a Binary Search Tree? I think I'll start a new thread for that one.
Will try.. :D

Savage
Sep 25 '07 #15

Ganon11
Expert 2.5K+
P: 3,652
Thanks a lot, Savage.
Sep 25 '07 #16

Expert 10K+
P: 11,448
Thanks a lot, Savage.
I'm a bit astonished; this thread wasn't about isomorphic trees at all; it was just
about a tedious attempt to create a random binary tree with n nodes. The fact
that you wanted to construct such a tree by building an ordered (search) tree is
just an artefact to construct a random tree.

Read up on Donald Knuth's "Searching and Sorting" (volume 3 of his old and
famous work), it's filled with theory, proofs and algorithms with just this.

kind regards,

Jos
Sep 25 '07 #17

P: 1
Ganon11,

By any chance are you in Data Structures and Algorithms at RPI? I am working on the exact same problem right now, and i was stuck so i went online to see if i could find some guidance. It sounds like we might be in the same class. : )

~cherry8707
Sep 26 '07 #18

Post your reply

Sign in to post your reply or Sign up for a free account.