Trouble with Isomorphism in Trees

[Ganon11]

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:

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

[Ganon11]

Also, does anyone know why I'm getting all these repeat values for my insertions?

[ilikepython]

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:

#include <iostream>
using namespace std;
 
const int MAX_SIZE = 10;
 
template <class T>
struct TreeNode {
    TreeNode<T> *left;
    TreeNode<T> *right;
    T data;
};
 
template <class T>
bool areIsomorphic(TreeNode<T> *first, TreeNode<T> *second);
 
template <class T>
void createTree(TreeNode<T> *node);
 
template <class T>
void insert(TreeNode<T> *node, T obj);
 
template <class T>
void printTree(TreeNode<T> *node);
 
int main() {
    srand((unsigned)time(NULL));
    TreeNode<int> *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;
}<snipped otheer wise post woudnt show>
 

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.

[Laharl]

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.

[Ganon11]

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:

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

template <class T>
TreeNode<T>::~TreeNode() {
    delete left;
    delete right;
}

[RRick]

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.

[Ganon11]

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:

template <class T>
void createTree(TreeNode<T> **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.

[ilikepython]

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:

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

template <class T>
TreeNode<T>::~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():

template <class T>
void insert(TreeNode<T> *temp, T obj) {
    cout << "Entering insert with obj = " << obj << endl;
    if (temp == NULL) {
        temp = new TreeNode<T>;
        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); }
        }
    }
 

[Ganon11]

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?

[Ganon11]

OK, I figured out the problem has to be in my createTree and insert functions. Here is what they are as of today:

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

[Savage]

OK, I figured out the problem has to be in my createTree and insert functions. Here is what they are as of today:

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

[Savage]

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

[Savage]

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

[Ganon11]

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.

[Savage]

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

[Ganon11]

Thanks a lot, Savage.

[JosAH]

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

[cherry8707]

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