if the root of T2 is duplicated in T1,this code may give a wrong
answer....(as there is no provision of backtracking in case there is a mis
match after some matchings).....given above KMP is the best possible answer
i think..
On Wed, Jan 12, 2011 at 11:28 AM, pacific pacific <pacific4...@gmail.com>wrote:
> Here is my pseudo code :
> check( node t1 , node t2 )
> {
> if ( t1->data == t2->data)
> {
> return check( t1->left , t2->left ) && check(t1->right, t2->right) ;
> }
> else
> {
> return check(t1->left , t2) || check(t1->right , t2);
> }
> }
>
> time complexity : o(n) because each node in t1 needs to be visited once.let
> me know if this works.
>
>
> On Sun, Jan 9, 2011 at 1:30 PM, Harshal <hc4...@gmail.com> wrote:
>
>> @Nishaanth
>> T1 has millions of nodes. Suppose all the nodes of T1 are equal to root of
>> T2. Then u will have to check every where in T1. Putting height as
>> constraint, u will have to check only those nodes whose height is equal to
>> T2. It will reduce time complexity.
>>
>> Well m not able to think of better time complexity, another way would be:
>> Find Height of T2 ... O(k) //k is no. of nodes in T2
>> Find Height of each node in T1... O(N) //N is no. of nodes in T1
>>
>> now if p nodes in T1 have height same as T2, then we can find if a subtree
>> rooted at any of those p nodes are identical to T2 in O(pk) time.
>>
>> Thus total time complexity: O(N) + O(k) + O(pk).
>> correct me if I am wrong..
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Anoop Chaurasiya
CSE (2008-2012)
NIT DGP
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
