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;

_and the code that I wrote so far doesn't work._ Please, be more specific. Doesn't it compile properly? Does it compile but doesn't work the expected way? You may provide current output and expected output in the latter case. — Scheff's Cat, May 08 '20 at 15:37
I wouldn't do it like that. much too complicated. 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. It's about 6 lines of code. — john, May 08 '20 at 15:44
You've written a bool function, but almost the very first line you have `return;`, there's no boolean value there, so that's an error. — john, May 08 '20 at 15:46
@john You must admit that OPs solution (if working) would be stack friendly. Once, I proposed a recursive solution in an answer I got a complaint that C++ is not a functional language... ;-) — Scheff's Cat, May 08 '20 at 15:48
I edited the code and fixed the syntax errors, but the logic of the program is wrong. It always returns false. How can I fix it please? — SegmentationFault, May 08 '20 at 15:49
How can you know that the logic is wrong if your program even doesn't compile? — Scheff's Cat, May 08 '20 at 15:50
It does compile now that I edited it, it just gives a wrong output now. — SegmentationFault, May 08 '20 at 15:55
it does not, the problem is that the logic itself is wrong. my main problem is the fact it needs a tree object in the parameter. — SegmentationFault, May 08 '20 at 16:08
`bool BST::similarStructure(BST Tree2) { if (isEmpty()) { cout << "tree is empty\n"; return;` - You promise to return a `bool` and then don't. That's obviously a bug. What did you expect that code to do? — Jesper Juhl, May 08 '20 at 16:09
this can be done as node* p1 = root; node* p2 = Tree2.root; if (p1 == NULL && p2 == NULL) { return true; } if (p1 == NULL && p2 != NULL || p1 != NULL && p2 == NULL) { return false; } — SegmentationFault, May 08 '20 at 16:11
but even with this, the logic of the question is still incorrect — SegmentationFault, May 08 '20 at 16:11
@SegmentationFault What is the name of the method that checks that BSt is empty? Consider this statement while (!s1.IsEmpty() &&!s2.isempty()) { There are two different names. — Vlad from Moscow, May 08 '20 at 16:15

john · Answer 1 · 2020-05-08T15:55:40.533

0

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.

edited May 08 '20 at 15:55

answered May 08 '20 at 15:50

john

85,011
4
57
81

The code you replied with takes two node objects though. The function I need should take a BST object as a parameter, and this is why I'm stumped in the first place. – SegmentationFault May 08 '20 at 15:58
@SegmentationFault As I say above `you need to call it with the root node pointer of your two trees.` – john May 08 '20 at 15:58
Yes i know the this pointer, but my BST class code does not have anything to get the value of right or left, that is inside the node class – SegmentationFault May 08 '20 at 16:05
my code MUST have a tree object inside the function parameter – SegmentationFault May 08 '20 at 16:06
@SegmentationFault You're making problems where none exist. Write a function with a tree object as a function parameter (as you must do). In that function call my function with the roots of the two tree objects. You don't have to solve this by writing just one function. – john May 08 '20 at 17:30

score 0 · Answer 2 · answered May 08 '20 at 15:56

0

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)
}

answered May 08 '20 at 15:56

cigien

57,834
11
73
112

my code must have like in the main post a tree object in the parameter – SegmentationFault May 08 '20 at 16:06
Sure, just pass the `this` pointer as the other tree to this function. The code I provided is *supposed* to be a sketch of the underlying algorithm. I'll leave it up to you to figure out how to use it. – cigien May 08 '20 at 16:12
ive tried this, but the source code containing the BST class does not have access to the get right and get left. only the node class has this – SegmentationFault May 08 '20 at 16:17

score 0 · Answer 3 · answered May 08 '20 at 16:21

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;

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

3 Answers3