# To find if a tree is subtree of another

Page 1 of 1

## 6 Replies - 743 Views - Last Post: 24 May 2012 - 08:58 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=280514&amp;s=d550fff62449746e53eb8b8ed15144d4&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 indyarocks

Reputation: 0
• Posts: 104
• Joined: 07-March 12

# To find if a tree is subtree of another

Posted 24 May 2012 - 04:01 AM

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
{
flag = 0;
return flag;
}
//When only t2 is empty
{
flag = 0;
return flag;
}
Node *temp1, *temp2;
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)

Is This A Good Question/Topic? 0

## Replies To: To find if a tree is subtree of another

### #2 r.stiltskin

• D.I.C Lover

Reputation: 1831
• Posts: 4,927
• Joined: 27-December 05

## Re: To find if a tree is subtree of another

Posted 24 May 2012 - 06:59 AM

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.

### #3 jimblumberg

Reputation: 3044
• Posts: 9,280
• Joined: 25-December 09

## Re: To find if a tree is subtree of another

Posted 24 May 2012 - 07:00 AM

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

### #4 indyarocks

Reputation: 0
• Posts: 104
• Joined: 07-March 12

## Re: To find if a tree is subtree of another

Posted 24 May 2012 - 07:04 AM

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;
}
```

### #5 r.stiltskin

• D.I.C Lover

Reputation: 1831
• Posts: 4,927
• Joined: 27-December 05

## Re: To find if a tree is subtree of another

Posted 24 May 2012 - 08:35 AM

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.

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:

```
#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:
```
#define _BST_H

//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 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
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
private:
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(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
```

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.

### #6 indyarocks

Reputation: 0
• Posts: 104
• Joined: 07-March 12

## Re: To find if a tree is subtree of another

Posted 24 May 2012 - 08:41 AM

Indy.

### #7 r.stiltskin

• D.I.C Lover

Reputation: 1831
• Posts: 4,927
• Joined: 27-December 05

## Re: To find if a tree is subtree of another

Posted 24 May 2012 - 08:58 AM

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.