Checking whether Subtree or not!

I know what subtree is brooo…but pls check sample on this page:

Check if subtree | Practice | GeeksforGeeks

both your queries are asnwered in sample tc…just have look and then tell me whats the difference if still i am wrong @akshitm16

What do you think the answer to the tc which I gave should be?

1 Like

Is your test case failing due to TLE???

His logic is incorrect and I have already provided a tc where it fails.

1 Like

okay got you…answer should be 0…
But pls help modify the above code @akshitm16


NO WA in case which is too long to be displayed on GFG @humane

Your code fails on this test case

How to handle this excepion tc @humane @akshitm16 @ssjgz

As N=10000 You can go for O(N^2) complexity
and try to do it with level order at every vertex which is a possibility for starting node
This will work if you handle cases correctly

The above algorithm can be extended to handle such cases by adding a special character whenever we encounter NULL in inorder and preorder traversals.
Try to think about think (taken from gfg).

what if there were any duplicates in any tc @humane


ok bro will work on this @akshitm16

with duplicates - O(N^2)
without duplicates - O(N)

Also don’t use this

inmain.find(insub)!=string::npos

This would give TLE.

1 Like

yes just now optimised with $ sign and now tle! What to do @akshitm16

Did you use KMP? Can you send the code?

code is posted above in post #1
NO KMP. i dont know KMP…just .find function
just added $ functionality @akshitm16

Use KMP search and then try. If you don’t know KMP learn it.

Also-

1 Like

what is difference between .find and strstr…will it help? @akshitm16
else i will study KMP now

Not so good with the technicalities of C++ but I guess both use naive searching.
Ask @ssjgz

1 Like

The time complexities of std::string::find and strstr are not specified.

However, in practice it seems that std::string::find is generally implemented “naively” i.e. \mathcal{O}(N \times M):

but according to one guy, gcc’s strstr uses an asymptotically better algorithm:

and so might actually work in situations where std::string::find gets TLE.

3 Likes

c++ reference says it’s naive searching

1 Like