[indyarocks]

Hi,

I'm trying to solve a problem, where we can find,if we are given two trees, if second is subtree of first.
Here is basic implementation my BST. Implemented in one go, without any error

Now, I'm trying to write another function, which can solve the problem I have stated above:

//Checks if second tree is subtree of first.
//Friend of class "BST". To use pHead

bool compareSub(Node *p,Node *q);//Helper for CheckSubTree operator overloaded function

bool CheckSubTree(BST t1, BST t2)
{
    static bool flag = 0;   //Assume that t2 is not subtree of t1
    //When both tree are empty
    if(t1.pHead == NULL && t2.pHead == NULL)
    {
        flag = 0;
        return flag;
    }
    //When only t2 is empty
    if(t2.pHead == NULL)
    {
        flag = 0;
        return flag;
    }
    Node *temp1, *temp2;
    temp1 = t1.pHead;
    temp2 = t2.pHead;
    while(temp1 != NULL)
    {
        if(temp1->data == temp2->data) //If data at nodes are same then
        {                              //compare the rest of data
            flag = compareSub(temp1,temp2);
            return flag;
        }
        if(temp1->data > temp2->data)
        {
            temp1 = temp1->left;
        }
        else
        {
            temp1 = temp1->right;
        }
    }
    //If flag was not set by above while loop, implies, t2 is not subtree of t1
    return flag;
}

bool compareSub(Node *p,Node *q)//Helper for CheckSubTree operator overloaded function
{
    static bool flag1 = 1;
    if(p == NULL && q == NULL)
    return flag1;

    if(p->data == q->data && flag1 == 1)
    {
        flag1 = compareSub(p->left,q->left);
        flag1 = compareSub(p->right,q->right);
    }
    else flag1 = 0;
    return flag1;
}

I have attached updated BinaryTree.hpp header file below. (includes "friend bool CheckSubTree(BST t1, BST t2);" in BST class). I have also attached the other two files, main.txt and SubTree.txt, just in case you wanna give it a local run.
Its giving segmentation fault, when the execution goes to compareSub(Node *p,Node *q. I've implemented whole thing on my own, so this may not be the most efficient way to do it. Can anybody point out my mistake. I'm also trying to debug it.
Here is the stack trace:

#0 77A415DE	ntdll!LdrQueryProcessModuleInformation() (C:\windows\system32\ntdll.dll:??)
#1 77A415DE	ntdll!LdrQueryProcessModuleInformation() (C:\windows\system32\ntdll.dll:??)
#2 77A3014E	ntdll!LdrFindResource_U() (C:\windows\system32\ntdll.dll:??)
#3 00000000	0x0028f8cc in ??() (??:??)
#4 00000000	0x0028f91c in ??() (??:??)
#5 00000000	0x00000000 in ??() (??:??)

Attached File(s)

•  BinaryTree.txt (7.21K)
  Number of downloads: 31
•  main.txt (3.46K)
  Number of downloads: 25
•  SubTree.txt (1.46K)
  Number of downloads: 32

[r.stiltskin]

On line 47 & 48

    if(p == NULL && q == NULL)
    return flag1;

you return if BOTH p and q are NULL. What happens if only 1 of them is NULL? In that case you go ahead and try to access p->data and q->data (but one of them doesn't exist).

And by the way, you are at the point where you should learn how to properly compile multi-file programs -- not #include all the files together into a single compilation unit.

[jimblumberg]

In compareSub() what happens if q is NULL but p is not? Or if p is NULL and q is not? The program is segfaulting for me because q is NULL at line 50 in the above code. Shouldn't you be insuring that both your lists contain information. Maybe an OR instead of an AND is required on line 47.

Jim

[indyarocks]

r.stiltskin, on 24 May 2012 - 06:59 AM, said:

And by the way, you are at the point where you should learn how to properly compile multi-file programs -- not #include all the files together into a single compilation unit.

Thanks Stilt. Can you please give me some guideline for this ?

jimblumberg, on 24 May 2012 - 07:00 AM, said:

Maybe an OR instead of an AND is required on line 47.

Actually here, both OR and AND are required. AND to check if its really a subtree. OR to check if either of p or q ends earlier at NULL.

Changed the code to:

bool compareSub(Node *p,Node *q)//Helper for CheckSubTree operator overloaded function
{
    static bool flag1 = 1;
    if(p == NULL && q == NULL)
    return flag1;

    if(p == NULL || q == NULL)
    {
        flag1 = 0;
        return flag1;
    }

    if(p->data == q->data && flag1 == 1)
    {
        flag1 = compareSub(p->left,q->left);
        flag1 = compareSub(p->right,q->right);
    }
    else flag1 = 0;
    return flag1;
}

[r.stiltskin]

indyarocks, on 24 May 2012 - 10:04 AM, said:

r.stiltskin, on 24 May 2012 - 06:59 AM, said:

And by the way, you are at the point where you should learn how to properly compile multi-file programs -- not #include all the files together into a single compilation unit.

Thanks Stilt. Can you please give me some guideline for this ?

Some guidelines:

Put class & struct definitions in a header file -- .h or .hpp -- and DON't #include other headers in it. If necessary, you can use advance declarations to declare other classnames that are needed by this header.

Use header guards. (See Google for explanation.)

Put class & struct implementations in a source (.cpp) file and #include any necessary headers there.

To minimize possible name conflicts, limit your using directives. Either use explicit scope operators (e.g. std::cout), or at least limit the directive to the specific objects (e.g. using std::out;) instead of a "blanket" using namespace std;.

Here's a "saner" way to organize your program:

Your driver program -- driver.cpp:

#include "BST.h"
#include <iostream>
using std::ostream;
using std::cout;
using std::endl;


//#include "BinaryTree.cc"  // don't #include source files in other source files
//#include "SubTree.cc"

int main()
{
    BST tt1;
    tt1.Insert(3);
    tt1.Insert(9);
    tt1.Insert(2);
    tt1.Insert(6);
    tt1.Insert(4);
// ...

BST.h:

#ifndef _BST_H           // Google "header guards" or "include guards" for explanation
#define _BST_H

//#include <iostream>    // don't #include headers in other headers
//using namespace std;  // not needed 

class ostream;  // advance declaration of ostream so we can use its name (in your friend declaration)

struct Node
{
    Node *left;
    int data;
    Node *right;
};

class BST
{
    public:
//    BST() { pHead = NULL;}          //Constructor   // don't put implementation in the header
    BST();                          //Constructor     // declaration only
//  BST(const BST&);                //Copy constructor
//    ~BST() { destruct(pHead);}      //Destructor    // don't put implementation in the header
    ~BST();                         //Destructor      // declaration only

    void destruct(Node *);          //Destructor Helper
    bool operator== (const BST &);  //Equality check operator overloading function.
    bool compare(Node *p,Node *q);  //Helper for "==" operator overloaded function
    friend ostream& operator<< (ostream&, Node&);//To print the data of a Node
    void Search(int num, bool &found, Node *&parent, Node *&x);    //Helper for Insert and Delete function
    void Insert(int num);           //Insert a number into tree
    void Delete(int num);           //Delete a number from tree
    void operator= (BST &);        // "=" operator overloading
    Node * copy(Node *p,Node *q);   //Helper copy funtion for "=" operator
    void Traversal();               //Tree traversal
    void In(Node *);                //In order traversal
    void Pre(Node *);               //Pre order traversal
    void Post(Node *);              //Post order traversal
//    static int GetCount() { return count;}//Public method to get the count of nodes  // don't put implementation in the header
    static int GetCount();          //Public method to get the count of nodes      // declaration only
    friend bool CheckSubTree(BST t1, BST t2); // So that CheckSubTree can access the compare function
                                              //and to use pHead.
    private:
    Node *pHead;                    //Root Node
    static int count;               //Count of Nodes in tree
};

#endif

BinaryTree.cpp:

#include "BST.h"
#include <iostream>
using std::ostream;
using std::cout;
using std::cin;
using std::endl;

int BST::count = 0;                 //Initialize static counter.  (Don't re-use static keyword here.)

BST::BST() { pHead = NULL;}          //Constructor

BST::~BST() { destruct(pHead);}      //Destructor

//BST(const BST&);                //Copy constructor

int BST::GetCount() { return count;}//Public method to get the count of nodes

// ...

To compile this on the command line, you would use a command like:

g++ -Wall -Wextra -pedantic driver.cpp BinaryTree.cpp -o driver

or read a tutorial about make (Makefiles).

If you use an IDE, it will take care of the compilation and building if you correctly add all of the files to the project.

[indyarocks]

Thanks a lot Stilt. I'll follow your advise. In case any doubt, I'll ask you again.

Indy.

[r.stiltskin]

By the way, here's a quote from Stroustrup's C++ Style and Technique FAQ:

Bjarne Stroustrup said:

Should I use NULL or 0?

In C++, the definition of NULL is 0, so there is only an aesthetic difference. I prefer to avoid macros, so I use 0. Another problem with NULL is that people sometimes mistakenly believe that it is different from 0 and/or not an integer. In pre-standard code, NULL was/is sometimes defined to something unsuitable and therefore had/has to be avoided. That's less common these days.
If you have to name the null pointer, call it nullptr; that's what it's going to be called in C++0x. Then, "nullptr" will be a keyword.

And you might want to glance over the rest of that document.