Need help writing a function to check if two BSTs have the same structure

Question

I'm trying write a function to check if two trees have the same structure, regardless of values, and the code that I wrote so far doesn't work. Any help or pointers (pun intended) would be greatly appreciated.

template <class T>
bool BST<T>::similarStructure(BST Tree2) {
    if (isEmpty()) {
        cout << "tree is empty\n";
        return;
    }

    StackArray<node<T>> s1, s2; // s1 for traversal,, s2 for printing

    s1.Push(root);
    s2.Push(tree2.root);
    while (!s1.IsEmpty() &&!s2.isempty()) {
        node<T> n = s1.Pop();
        node<T> n1=s2.Pop();
        if (n->right != NULL && n1->right!=NULL){
            s1.Push(n->right);
            s2.Push(n1->right); }
         else{
           return false;}

        if (n->left != NULL && n->left!=NULL){
            s1.Push(n->left); 
            s2.Push(n1->left);}
        else{
            return false;}

    }
    return true;

Answer 1

I must be in a generous mood.

A simple in-order traversal will solve the problem. Just check at each node that the left field is null or not null in both trees, same test for the right field, then recurse.

This template function does the work, you need to call it with the root node pointer of your two trees.

template <class T>
bool similarStructure(node<T>* x, node<T>* y) const
{
    if (x == y)
        return true;
    if (x == nullptr || y == nullptr)
        return false;
    return similarStructure(x->left, y->left) && similarStructure(x->right, y->right);
}

Untested code.

Answer 2

Here's a sketch of what you can try out:

bool similarStructure(BST t1, BST t2)
{
  return !(t1.root ^ t2.root) 
         && t1.root 
         && similarStructure(t1.root->left, t2.root->left)
         && similarStructure(t1.root->right, t2.root->right)
}

Answer 3

Your function is invalid because at least in this part of the function

template <class T>
bool BST<T>::similarStructure( BST Tree2 ) 
{
    if (isEmpty()) {
        cout << "tree is empty\n";
        return;
    }
    //...

it returns nothing though the function has the return type bool.

Using your approach the function can look the following way

template <class T>
bool BST<T>::similarStructure( const BST &Tree2 ) const 
{
    if ( isEmpty() && Tree2.isEmpty() ) return true;

    StackArray<node<T>> s1, s2;

    s1.Push( root );
    s2.Push( tree2.root );

    bool theSame = true;

    while ( theSame && !s1.isEmpty() ) 
    {
        node<T> n  = s1.Pop();
        node<T> n1 = s2.Pop();

        theSame = ( n->right != NULL ) == ( n1->right != NULL );

        if ( theSame && n->right != NULL )
        { 
            s1.Push( n->right );
            s2.Push( n1->right );
        }

        if ( theSame )
        {
            theSame == ( n->left != NULL ) == ( n->left != NULL );
            if ( theSame && n->left != NULL )
            {
                s1.Push( n->left ); 
                s2.Push( n1->left );
            }
        }
    }

    return theSame;
}

Pay attention to that the function is declared with the qualifier const. It means that the member function isEmoty of the class BST<T> also shall be declared with the qualifier const.

bool isEmpty() const;