# Checking whether Subtree or not!

https://practice.geeksforgeeks.org/problems/check-if-subtree/1/

``````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.

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

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

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

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

In bst also there can be duplicates.

Can you verify your logic on this tc-

1 Like

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

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

â€śInternetâ€ť says lots of things

3 Likes

okâ€¦ but lets get back to the question @ssjgz PLease point mistake in my code

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

1 Like

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

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.

1 Like

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

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

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

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