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 <[email protected]>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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
