449,220 Members | 1,798 Online
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

 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 first, TreeNode 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 #include  using namespace std;   const int MAX_SIZE = 10;   template  struct TreeNode {     TreeNode *left;     TreeNode *right;     T data; };   template  bool areIsomorphic(TreeNode *first, TreeNode *second);   template  void createTree(TreeNode *node);   template  void insert(TreeNode *node, T obj);   template  void printTree(TreeNode *node);   int main() {     srand((unsigned)time(NULL));     TreeNode *first, *second;     createTree(first);     createTree(second);     printTree(first);     cout << endl << endl;     printTree(second);     cout << endl << endl;     if (areIsomorphic(first, second)) {         cout << "The trees are isomorphic." << endl;     } else {         cout << "The trees are not isomorphic." << endl;     }     return 0; }   template  void createTree(TreeNode *node) {     cout << "Entering createTree..." << endl;     node = new TreeNode;     for (int i = 0; i < MAX_SIZE; i++)         insert(node, rand() % 50); }   template  void insert(TreeNode *temp, T obj) {     cout << "Entering insert with obj = " << obj << endl;     if (temp == NULL) temp->data = obj;     else {         if (temp->data < obj) {             if (temp->right == NULL) {                 TreeNode *newNode = new TreeNode;                 newNode->data = obj;                 temp->right = newNode;             } else insert(temp->right, obj);         } else {             if (temp->left == NULL) {                 TreeNode *newNode = new TreeNode;                 newNode->data = obj;                 temp->left = newNode;             } else insert(temp->left, obj);         }     } }   template  void printTree(TreeNode *node) {     cout << "Entering printTree..." << endl;     if (node != NULL) {         printTree(node->left);         cout << " " << node->data;         printTree(node->right);     } }   template  bool areIsomorphic(TreeNode *first, TreeNode *second) {     cout << "Entering areIsomorphic..." << endl;     if (first == NULL && second == NULL) return true;     else if (first == NULL || second == NULL) return false;     else if (first->left == NULL && second->left == NULL && first->right == NULL && second->right == NULL) return true;     else if (areIsomorphic(first->left, second->left) && areIsomorphic(first->right, second->right)) return true;     else if (areIsomorphic(first->left, second->right) && areIsomorphic(first->right, second->left)) return true;     else return false; }   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
17 Replies

 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

 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 first, TreeNode 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 #include  using namespace std;   const int MAX_SIZE = 10;   template  struct TreeNode {     TreeNode *left;     TreeNode *right;     T data; };   template  bool areIsomorphic(TreeNode *first, TreeNode *second);   template  void createTree(TreeNode *node);   template  void insert(TreeNode *node, T obj);   template  void printTree(TreeNode *node);   int main() {     srand((unsigned)time(NULL));     TreeNode *first, *second;     createTree(first);     createTree(second);     printTree(first);     cout << endl << endl;     printTree(second);     cout << endl << endl;     if (areIsomorphic(first, second)) {         cout << "The trees are isomorphic." << endl;     } else {         cout << "The trees are not isomorphic." << endl;     }     return 0; }   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

 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 template  void createTree(TreeNode *node) {     cout << "Entering createTree..." << endl;     for (int i = 0; i < MAX_SIZE; i++)         insert(node, rand() % 50); }   template  void insert(TreeNode *temp, T obj) {     cout << "Entering insert with obj = " << obj << endl;     if (temp == NULL) {         temp = new TreeNode;         temp->data = obj;     } else {         if (temp->data < obj) {             if (temp->right == NULL) {                 TreeNode *newNode = new TreeNode;                 newNode->data = obj;                 temp->right = newNode;             } else insert(temp->right, obj);         } else {             if (temp->left == NULL) {                 TreeNode *newNode = new TreeNode;                 newNode->data = obj;                 temp->left = newNode;             } else insert(temp->left, obj);         }     } } 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 template  TreeNode::~TreeNode() {     delete left;     delete right; } Sep 24 '07 #5

 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

 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 template  void createTree(TreeNode **node) {     cout << "Entering createTree..." << endl;     for (int i = 0; i < MAX_SIZE; i++)         insert(*node, rand() % 50); } and I'm now calling it with createTree(&first). Same errors. Sep 25 '07 #7

 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 template  void createTree(TreeNode *node) {     cout << "Entering createTree..." << endl;     for (int i = 0; i < MAX_SIZE; i++)         insert(node, rand() % 50); }   template  void insert(TreeNode *temp, T obj) {     cout << "Entering insert with obj = " << obj << endl;     if (temp == NULL) {         temp = new TreeNode;         temp->data = obj;     } else {         if (temp->data < obj) {             if (temp->right == NULL) {                 TreeNode *newNode = new TreeNode;                 newNode->data = obj;                 temp->right = newNode;             } else insert(temp->right, obj);         } else {             if (temp->left == NULL) {                 TreeNode *newNode = new TreeNode;                 newNode->data = obj;                 temp->left = newNode;             } else insert(temp->left, obj);         }     } } 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 template  TreeNode::~TreeNode() {     delete left;     delete right; } 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 template  void insert(TreeNode *temp, T obj) {     cout << "Entering insert with obj = " << obj << endl;     if (temp == NULL) {         temp = new TreeNode;         temp->data = obj; }        else {         if (temp->data < obj) {             insert(temp->right, obj); }    // go right to insert since you handle if pointer is NULL at the top of the function           else {          insert(temp->left, obj); }         }     }   Sep 25 '07 #8

 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

 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 void createTree(TreeNode **node) {     cout << "Entering createTree..." << endl;     (*node) = new TreeNode;     (*node)->data = rand() % 50;     for (int i = 1; i < MAX_SIZE; i++)         insert(*node, rand() % 50); }   void insert(TreeNode *temp, int obj) {     cout << "Entering insert with obj = " << obj << endl;     if (temp == NULL) {         temp = new TreeNode;         temp->data = obj;     } else {         cout << "temp->data = " << temp->data << endl;         if (temp->data < obj)             insert(temp->right, obj);         else if (obj < temp->data)             insert(temp->left, obj);         else             ;     } } 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

 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 void createTree(TreeNode **node) {     cout << "Entering createTree..." << endl;     (*node) = new TreeNode;     (*node)->data = rand() % 50;     for (int i = 1; i < MAX_SIZE; i++)         insert(*node, rand() % 50); }   void insert(TreeNode *temp, int obj) {     cout << "Entering insert with obj = " << obj << endl;     if (temp == NULL) {         temp = new TreeNode;         temp->data = obj;     } else {         cout << "temp->data = " << temp->data << endl;         if (temp->data < obj)             insert(temp->right, obj);         else if (obj < temp->data)             insert(temp->left, obj);         else             ;     } } 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

 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

 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

 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

 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

 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