thank you for telling the unworkability of my algo.
i did not see the puzzle completely. my algo works only for BST.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 8:49 PM, Lucifer <sourabhd2...@gmail.com> wrote:
> @All
>
> [ Let the tree to be searched in be 'T' and the subtree to be matched
> be 'S']
>
> If i understood the previous posts correctly.. then basically we
> discussed about 2 methods:
> 1) Brute force, wherein we consider each node of the 'T' as the root
> of new subtree and try to compare it with 'S'.
> Complexity - O( |T| * |S| ) ... ( |X| = size of 'X' )
>
> 2) Preorder with special characters...
> Time complexity:-
> Time taken to generate the preordered string for
> 'T' :- 2* |T| + 1
> Time taken to generate the preordered string for
> 'S' :- 2* |S| + 1
> Time taken to find a match : O(2* |T|) + O(2* |S|)
> Hence, total time complexity : O(|T|) .. [assuming that |T| >=|
> S| ]
>
> Space complexity: 2*( |T| + |S| + 1)
>
> I think we can come up with a third method where the time complexity
> will be of the order of O(|T|) with constant space..
> Here is the idea,
>
> As we know that the subtree in the question is a perfect subtree, we
> can use it to develop a O(|T|) algo..
> If we know the count of nodes for each perfect subtree of |T| then for
> all those subtrees having the count equal to |S| we will perform a
> check to see if the subtrees match, otherwise we won't..
>
> Basic operations:
> 1) Count the no. of nodes of |S| : CountNodes(node * root) ( Time
> Complexity : |S|)
> 2) Check whether 2 trees are equal : isTREqual(node *T1, node *T2)
> ( Time Complexity : |S|, as we are going to check only for those
> subtrees of |T| whose count is equal to |S|)
> 3) Modify the CountNodes(node *root) API to calculate the count of the
> subtrees as well as check with the subtree of 'T' is equal to 'S' when
> the counts match.
>
> Regarding time complexity of the above algo:
> As we already know the time complexity of operations 1 and 2, lets
> talk about operation 3.
> The count procedure will take |T| time in total...
> What about the match procedure ?
> Say that we have identified subtrees T1, T2...Tn.. whose count is
> equal to |S|, hence the time taken by the tree match procedure will be
> |S| * (n)..
> Lets look at this derivation in a slightly different way exploiting
> one of the properties of the found subtrees:
> Now, as we know that all the subtrees of T having the same node count |
> S| can't share nodes among them...
> hence,
> |T1| + |T2| + ... |Tn| <= |T| , i.,e |S| * (n) <= |T| , equality holds
> when S = T..
> Hence Time complexity (for operation 3) is equal to 2*|T|..
>
> Total complexity: time taken by operation (1) + (3)
> : |S| + 2*|T| = O(|T|)
>
> -------------------------------
> Pseudocode:
>
> // I m not jolting down the code for CountNodes and isTREqual..
> // Also, currently assuming that |S| and |T| are not null trees.. well
> this special case can be handled, if required.. but i don't think its
> a valid use case..
>
>
> bool areTreesSame(node *T, node *S, int countS, int *nCount)
> {
> int leftCount=0, rightCount=0;
> if (T == NULL)
> return false;
> if ( areTreesSame(T-> left, S, countS, &leftCount) ||
> areTreesSame(T-> right, S, countS, &rightCount)
> )
> return true;
> else
> {
> *nCount = leftCount+rightCount+1;
> if(nCountS == *nCount)
> return isTREqual(T, S);
> else
> return false;
> }
> }
>
> -----------------------------------
>
>
>
> On Mar 21, 5:04 pm, Dheeraj Sharma <dheerajsharma1...@gmail.com>
> wrote:
> > Yeah..i wrote sumthig similar..i placed L for left null and R for
> > right null..and then checked for substring in preorder traversal..i
> > dont know if its correct or not..
> >
> > On 3/21/12, atul anand <atul.87fri...@gmail.com> wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > > @amrit : i guess this will work.
> >
> > > On Wed, Mar 21, 2012 at 1:51 PM, amrit harry <dabbcomput...@gmail.com
> >wrote:
> >
> > >> i have an idea to solve this.
> > >> use preorder traversal and a sentinal(#) on the place of Null nodes.
> > >> lets take a example
> > >> Main tree 1
> > >> subtree 1
> > >> 2 3
> > >> 2
> > >> 4
> > >> 3
> >
> > >> preorder travesal for Main: 12##34### for sub tree 12#3###
> > >> now chk for the sub string in Main string
> >
> > >> one more case
> > >> Main 1
> > >> / \
> > >> 3 4
> > >> / \
> > >> 5 1
> > >> / \
> > >> 3 4
> > >> preorder traversal= 1353##4##1##4##
> > >> sub
> > >> 5
> > >> / \
> > >> 3 4
> >
> > >> preorder traversal 53##4##
> > >> now this substring exist in Main substring so it is a sub tree....
> > >> correct me if me wrong.
> > >> Thanks
> > >> Amrit
> > >> On Wed, Mar 21, 2012 at 1:34 PM, amrit harry
> > >> <dabbcomput...@gmail.com>wrote:
> >
> > >>> @shady consider this case
> > >>> Main tree 1
> > >>> subtree 1
> > >>> 2 3
> > >>> 2
> > >>> 4
> > >>> 3
> >
> > >>> preorder of Main= 1234 subtree= 123 but not subtree
> > >>> On Wed, Mar 21, 2012 at 1:24 PM, shady <sinv...@gmail.com> wrote:
> >
> > >>>> seems correct with pre-order traversal.... if not give some example
> >
> > >>>> On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur
> > >>>> <tmahesh...@gmail.com>wrote:
> >
> > >>>>> First Tree:
> > >>>>> 1
> > >>>>> 2 3
> > >>>>> 4 5 6 7
> >
> > >>>>> Inorder traverse will be : 4251637
> >
> > >>>>> Second Tree:
> > >>>>> 6
> > >>>>> 1 3
> >
> > >>>>> Inorder traversal is 163.
> >
> > >>>>> But they second tree is not subset. let me know if i got the
> question
> > >>>>> wrong.
> >
> > >>>>> On Wed, Mar 21, 2012 at 10:27 AM, shady <sinv...@gmail.com> wrote:
> >
> > >>>>>> @Sid +100
> >
> > >>>>>> On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh <
> > >>>>>> siddharam....@gmail.com> wrote:
> >
> > >>>>>>> get the inorder traversal both tree (into strings) check weather
> one
> > >>>>>>> string substring of other if yes then one tree is sub tree of
> other.
> >
> > >>>>>>> Thank you,
> > >>>>>>> Sid.
> > >>>>>>> phone:+91-8971070727,
> > >>>>>>> +91-9916809982
> >
> > >>>>>>> On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA <
> > >>>>>>> hpahuja.mn...@gmail.com> wrote:
> >
> > >>>>>>>> bool isSubtree(Tree * A,Tree *B)
> > >>>>>>>> {
> >
> > >>>>>>>> if(!B) return true;
> > >>>>>>>> if(!A)return false;
> > >>>>>>>> if(A->data==B->data)
> > >>>>>>>> return (isSubtree(A->left,B->left)
> > >>>>>>>> && isSubtree(A->right,B->right));
> > >>>>>>>> else
> > >>>>>>>> return (isSubtree(A->left,B) &&
> isSubtree(A->right,B));
> > >>>>>>>> }
> >
> > >>>>>>>> }
> >
> > >>>>>>>> On Wed, Mar 21, 2012 at 2:33 AM, Don <dondod...@gmail.com>
> wrote:
> >
> > >>>>>>>>> bool equals(node *t1, node *t2)
> > >>>>>>>>> {
> > >>>>>>>>> return (t1 && t2) ? (t1->value == t2->value) &&
> equals(t1->left,
> > >>>>>>>>> t2-
> > >>>>>>>>> >left) && equals(t1->right, t2->right) : !t1 && !t2;
> > >>>>>>>>> }
> >
> > >>>>>>>>> bool check(node *t1, node *subtree)
> > >>>>>>>>> {
> > >>>>>>>>> return t1 ? equals(t1, subtree) || check(t1->left, subtree) ||
> > >>>>>>>>> check(t1->right, subtree) : !subtree;
> > >>>>>>>>> }
> >
> > >>>>>>>>> On average this is the same as a traversal, but worst case
> could be
> > >>>>>>>>> very slow. Imagine a large tree with millions of nodes, where
> all
> > >>>>>>>>> the
> > >>>>>>>>> nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1
> and
> > >>>>>>>>> one
> > >>>>>>>>> node at the far right of the tree = 2. It would require a
> lengthy
> > >>>>>>>>> comparision at each node which would ultimately find no
> matching
> > >>>>>>>>> sub
> > >>>>>>>>> tree.
> >
> > >>>>>>>>> If they are binary search trees, it could be more efficient.
> Did
> > >>>>>>>>> you
> > >>>>>>>>> mean to ask about binary search trees?
> >
> > >>>>>>>>> Don
> >
> > >>>>>>>>> On Mar 20, 7:24 am, Dheeraj Sharma <
> dheerajsharma1...@gmail.com>
> > >>>>>>>>> wrote:
> > >>>>>>>>> > How to check if one binary tree is a sub tree of other?
> > >>>>>>>>> > Any Solution other then bruteforce?
> > >>>>>>>>> > Prototype
> > >>>>>>>>> > bool check(node *t1,node *subtree)
> >
> > >>>>>>>>> > --
> > >>>>>>>>> > Sent from my mobile device
> >
> > >>>>>>>>> > *Dheeraj Sharma*
> >
> > >>>>>>>>> --
> > >>>>>>>>> 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.
> >
> > >>>>>>>> --
> > >>>>>>>> HARSHIT PAHUJA
> > >>>>>>>> M.N.N.I.T.
> > >>>>>>>> ALLAHABAD
> >
> > >>>>>>>> --
> > >>>>>>>> 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.
> >
> > >>>>>>> --
> > >>>>>>> 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.
> >
> > >>>>>> --
> > >>>>>> 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.
> >
> > >>>>> --
> > >>>>> 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.
> >
> > >>>> --
> > >>>> 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.
> >
> > >>> --
> > >>> AMRIT
> >
> > >> --
> > >> AMRIT
> >
> > >> --
> > >> 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.
> >
> > > --
> > > 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.
> >
> > --
> > Sent from my mobile device
> >
> > *Dheeraj Sharma*
>
> --
> 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.
>
>
--
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.
