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