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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
