Yes, you are right. Good catch.
On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:
>
> Amazing solution Don, thank you :) You missed a small check in the code:
> if(t1[0] != t2[0]) return 0;
>
>
> On Tue, Jul 9, 2013 at 11:27 PM, Don <dond...@gmail.com <javascript:>>wrote:
>
>> The trees would be the same if
>> 1. The root is the same
>> 2. The left and right subtrees are both the same
>>
>> bool sameBstFormed(intVector t1, intVector t2)
>> {
>> if (t1.size() != t2.size()) return false; // Trees with
>> different number of nodes can't be the same
>> if (t1.size() == 0) return true; // Two empty trees are
>> equal
>> if (t1.size() == 1) return t1[0] == t2[0]; // Single node trees
>>
>> // Partition left and right subtrees
>> intVector left1, right1, left2, right2;
>> for(int i = 1; i < n1; ++i)
>> {
>> if (t1[i] < t1[0]) left1.add(t1[i]);
>> else right1.add(t1[i]);
>> if (t2[i] < t2[0]) left2.add(t2[i]);
>> else right2.add(t2[i]);
>> }
>>
>> return sameBstFormed(left1, left2) && sameBstFormed(right1, right2);
>>
>> }
>>
>> On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:
>>>
>>> I came across this question on careercup: how do we go about finding
>>> whether the BSTs formed by the given input order would be identical or not
>>> without actually forming the tree?
>>>
>>> Link:
>>> http://www.careercup.**com/question?id=19016700<http://www.careercup.com/question?id=19016700>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+...@googlegroups.com <javascript:>.
>>
>>
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
