Checking whether Subtree or not!

general
, ,
1

Check if subtree | Practice | GeeksforGeeks

void inorder(Node *root, string &x)
{
    if(root)
    {
        inorder(root->left,x);
        x=x+to_string(root->data);
        inorder(root->right,x);
    }
}

void preorder(Node *root, string &y)
{
    if(root)
    {
        y=y+to_string(root->data);
        preorder(root->left,y);
        preorder(root->right,y);
    }
}
bool isSubTree(Node* T, Node* S)
{
    if(S==NULL) 
        return true;
    if(T==NULL)
        return false;
    string inmain, premain, insub, presub;
    inorder(T,inmain);
    preorder(T,premain);
    inorder(S,insub);
    preorder(S,presub);
    if(inmain==insub&&premain==presub)
        return true;
    else if(inmain.find(insub)!=string::npos&&premain.find(presub)!=string::npos)
        return true;
    else
        return false;
}

One TC is failing and that is also not completely visible on the GFG platform.
I want to know whether the code is correct or not and if WRONG, where is the logic going wrong?

Logic: Just checking inorder and preorder of both trees and checking whether it is a subset or not!

P.S. Please don’t provide me GFG article links of the same question. This is my own approach and I want help regarding this only.

2

help needed @ssjgz @alei @ssrivastava990 @vrishinvv @sudipandatta @akshitm16

3

This is my approach:
If all vertices are distinct ( which should be )
Then just find the vertex in the big tree which is equal to root of small tree ( if vertex not found then that is not a subtree )
So you got the starting points of the both the tree and now you need to compare
Just apply level order traversal simultaneously if at a point any node differs until level order of small tree is completed then it will not be a subtree

(by vertex i mean node)

If vertices are not distinct then complexity will be O(v^2) as you have to check every node as a starting possibility which is very inefficient obviously

1 Like
4

Everything is correct but it isn’t necessary that all vertices should be distinct. Can I ask why do you think so (I might be missing something) ?

1 Like
5

@akshitm16 @humane I just wanted to do by checking trversals… Can you help with above code I posted??

6

@humane No distinct cant be the possibility here as this is not BST!!!
@akshitm16 i think he assumed bst

7

In bst also there can be duplicates.

8

Can you verify your logic on this tc-

Subtree
Subtree1280Ă—960 37.3 KB

1 Like
9

In a Binary Search Tree (BST), all keys in left subtree of a key must be smaller and all keys in right subtree must be greater. So a Binary Search Tree by definition has distinct keys and duplicates in binary search tree are not allowed.

@akshitm16 Internet says this

10

See if you find preorder and inorder of both trees then the subtree’s pre and inorder will be subset somewhere in pre and inorder of larger tree @akshitm16

11

“Internet” says lots of things :slight_smile:

3 Likes
12

ok… but lets get back to the question :disappointed_relieved: @ssjgz PLease point mistake in my code

13

So according to your logic, answer should be Yes but in actual it is No.

1 Like
14

I have already given a tc where your code fails.

15

Yes it is true acc to judge too… see sample tc on questions page @akshitm16

16

I see you haven’t read the full article. Read the whole thing and and my test case as well. The article also mentions a similar tc as mine where your logic would fail and its possible solution. :slightly_smiling_face:

1 Like
18

but similar trees are also considered subtress acc to sample tc on question’s page @akshitm16

19

Not BST!!
I saw a similar question once just with distinct vertices

20

@humane see my code bro… I want to do by recursion only by checking traversal array

21

Please try to understand the test which I gave and read the definition of Subtree. I think you’re not clear with what a subtree is.

1 Like