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.
