Checking whether Subtree or not!

general
, ,
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
22

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

23

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

1 Like
24

Is your test case failing due to TLE???

25

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

1 Like
26

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

27

Your code fails on this test case

28

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

29

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

30

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

31

what if there were any duplicates in any tc @humane

ok bro will work on this @akshitm16

32

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

33

Also don’t use this

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

This would give TLE.

1 Like
34

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

35

Did you use KMP? Can you send the code?

36

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