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.
