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" <[email protected]> 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 <[email protected]> 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 [email protected]**.
>>>>
>>>>
>>>>
>>>
>>> --
> 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 [email protected].
>
>
>
--
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 [email protected].
