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.