You don't need to take vector for this you can have input in array also.
You just need to check the elements in each partition .
On 12-Jul-2013 8:27 PM, "Don" <dondod...@gmail.com> wrote:
> Can anyone modify this solution so that it does not duplicate the memory
> at each level of recursion?
>
> (Here is my solution with the fix mentioned above)
>
> typedef std::vector<int> btree;
>
> bool sameBstFormed(btree t1, btree t2)
> {
> bool result;
> if (t1.size() != t2.size()) result = false;
> else if (t1.size() == 0) result = true;
> else if (t1[0] != t2[0]) result = false;
> else if (t1.size() == 1) result = true;
> else
> {
> btree left1, right1, left2, right2;
> for(int i = 1; i < t1.size(); ++i)
> {
> if (t1[i] < t1[0]) left1.push_back(t1[i]);
> else right1.push_back(t1[i]);
> if (t2[i] < t2[0]) left2.push_back(t2[i]);
> else right2.push_back(t2[i]);
> }
> result = sameBstFormed(left1, left2) && sameBstFormed(right1,
> right2);
> }
> return result;
> }
>
> On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote:
>>
>> 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> 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**.
>>>>
>>>>
>>>>
>>>
>>> --
> 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.
>
>
>
--
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.
