One approach would be to convert both the trees to well formed flat-tree
representation and then reduce the problem to a substring matching one (can
use KMP/Boyer-Moore/Rabin-Karp for it).
eg.
1
2 3
4 5
is flattened to (using postorder traversal) (1 (2 4 .) (3 . 5))
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.
On Sun, Jan 9, 2011 at 12:10 PM, nishaanth <nishaant...@gmail.com> wrote:
> Do an inorder walk on T1 till you get the root of T2.
>
> Then do a simultaneous walks on both the trees till T2(smaller tree) is
> fully explored.
>
> If at any point you discover dissimilar nodes. print 'no'
> else print 'yes'
>
> One more issue is if duplicates are allowed, then we cant print 'no' with
> just one failure, repeat till you explore the bigger tree fully.
> Correct me if i am wrong.
>
>
> On Sat, Jan 8, 2011 at 9:31 PM, Harshal <hc4...@gmail.com> wrote:
>
>> Given two binary trees T1 and T2 which store character data, duplicates
>> allowed. You have to devise an algorithm to decide whether the T2 is a
>> subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.
>>
>> --
>> Harshal Choudhary,
>> III Year B.Tech Undergraduate,
>> Computer Science and Engineering,
>> National Institute of Technology Surathkal, Karnataka
>> India.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
