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