get the inorder traversal both tree (into strings) check weather one string substring of other if yes then one tree is sub tree of other.
Thank you, Sid. phone:+91-8971070727, +91-9916809982 On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA <hpahuja.mn...@gmail.com>wrote: > bool isSubtree(Tree * A,Tree *B) > { > > if(!B) return true; > if(!A)return false; > if(A->data==B->data) > return (isSubtree(A->left,B->left) > && isSubtree(A->right,B->right)); > else > return (isSubtree(A->left,B) && isSubtree(A->right,B)); > } > > > > > > > > > > > } > > On Wed, Mar 21, 2012 at 2:33 AM, Don <dondod...@gmail.com> wrote: > >> bool equals(node *t1, node *t2) >> { >> return (t1 && t2) ? (t1->value == t2->value) && equals(t1->left, t2- >> >left) && equals(t1->right, t2->right) : !t1 && !t2; >> } >> >> bool check(node *t1, node *subtree) >> { >> return t1 ? equals(t1, subtree) || check(t1->left, subtree) || >> check(t1->right, subtree) : !subtree; >> } >> >> On average this is the same as a traversal, but worst case could be >> very slow. Imagine a large tree with millions of nodes, where all the >> nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one >> node at the far right of the tree = 2. It would require a lengthy >> comparision at each node which would ultimately find no matching sub >> tree. >> >> If they are binary search trees, it could be more efficient. Did you >> mean to ask about binary search trees? >> >> Don >> >> On Mar 20, 7:24 am, Dheeraj Sharma <dheerajsharma1...@gmail.com> >> wrote: >> > How to check if one binary tree is a sub tree of other? >> > Any Solution other then bruteforce? >> > Prototype >> > bool check(node *t1,node *subtree) >> > >> > -- >> > Sent from my mobile device >> > >> > *Dheeraj Sharma* >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > HARSHIT PAHUJA > M.N.N.I.T. > ALLAHABAD > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.