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