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].
