/* From Cracking the
Coding Interview 4-7 */
/* You have two very large binary trees: T1, with millions of
nodes, and T2, with hundreds of nodes.
Create an algorithm to
decide if T2 is a subtree of T1 */
bool isIdentical(node * t1, node * t2) {
if (t1 == nullptr && t2
== nullptr) {
return true;
}
if (t1 == nullptr || t2 == nullptr) {
return false;
}
return (t1->value
== t2->value && isIdentical(t1->left, t2->left) &&
isIdentical(t1->right, t2->right));
}
bool isSecondSubtree(node * t1, node * t2) {
if (t2 == nullptr) {
return true;
}
if (t1 == nullptr) {
return false;
}
if
(isIdentical(t1, t2)) {
return true;
}
return (
isSecondSubtree(t1->left, t2) || isSecondSubtree (t1->right, t2));
}
No comments:
Post a Comment