My code fails with some input where the root tree contains over a hundred nodes, one of which is a leaf with value 29. The subroot tree is a single node with value 29. The issue is, when I run tests with the same input on my machine, the result is correct (true). The edge cases that I can think off (single node subtrees, subtrees containing values of the root of the subtree, etc) are all handled (as far as I can say). I just cannot spot the mistake.
Does anyone have any idea of what might be wrong here?
void test_for_subtree(struct TreeNode* root,
struct TreeNode* subRoot,
bool* is_subtree) {
if (!root && !subRoot) return;
if ((root && !subRoot) || (!root && subRoot) ||
(root->val != subRoot->val)) {
*is_subtree = false;
return;
}
test_for_subtree(root->left, subRoot->left, is_subtree);
if (!*is_subtree) return;
test_for_subtree(root->right, subRoot->right, is_subtree);
}
void match_and_test(struct TreeNode* root,
struct TreeNode* subRoot,
bool* is_subtree) {
if (!root) return;
if (root->val == subRoot->val) {
*is_subtree = true;
test_for_subtree(root, subRoot, is_subtree);
if (*is_subtree) return;
}
match_and_test(root->left, subRoot, is_subtree);
match_and_test(root->right, subRoot, is_subtree);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
bool is_subtree = false;
match_and_test(root, subRoot, &is_subtree);
return is_subtree;
}
full test set:
[29, 28, 30, 27, 29, 29, 31, 26, 26, 28, 28, 28, 28, 30, 32, 25, 25, 25, 25,
27, 29, null, 29, 29, 29 , null, 29, 29, 29, 31, null, 26, 24, 26, 26, 26,
null, 24, null, null, 26, 28, null, 28, 28, 30, 28, 30, 30, null, null, 30,
30, 30, 30, null, 32, 27, 27, null, 25, 25, null, null, 25, 27, 27, null,
null, null, null, 27, 27, 27, 29, null, null, null, 31, 29, null, 31, null,
29, 29, null, null, 29, 31, null, 29, 29, 31, null, 31, null, null, null, 28,
24, 24, 24, 26, 24, 24, null, 28, 26, 28, 26, null, null, null, 28, 28, null,
28, null, null, 28, 30, 32, null, 30, 28, 28, 28, null, null, null, null, 28,
30, 28, 28, null, null, null, null, 27, null, null, null, 23, 25, null, null,
null, null, null, null, null, null, 27, 27, null, null, null, 29, null, null,
null, null, 27, 29, null, 27, 27, null, null, null, null, 31, 29, 29, 27, 29,
null, 29, 27, 29, null, null, null, null, 27, null, null, 29, null, null, 22,
22, null, 26, null, null, 26, 28, 28, 28, null, 28, null, 28, null, 28, null,
null, null, null, null, null, null, 28, null, 28, 28, null, 30, null, null,
null, null, null, 26, null, 28, 30, 21, 23, null, null, null, 25, null, 27,
null, null, null, null, 27, 29, 27, 29, 27, 27, null, null, null, null, 29,
null, 27, null, null, null, 25, 27, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null, null, 28, null, null,
null, null, null, null, null, null, 26, null, null, 24, null, 28, null, null,
null, null, null, 23]
[29]
Comments (0)