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