# This question has one trap that is not included in the test cases

• I could be wrong but s is binary tree, not BST. There is also no assumption that every node has unique values. So if s has two children with the same value with t, and the right subtree is identical to t but not the left one, all recursive solutions that returns checkLeft && checkRight will give the wrong answer.

Like this:

s:
0
1 1
2 3 2

t:
1
2

My solution (32ms) looks long but it handles this case. Please feel free to point out my mistakes.

``````class Solution {
vector<TreeNode*> res;
public:
//first trap: there can be multiple root(t) in s, need to find them all
void findTinS(TreeNode* s, TreeNode*t) {
if(!s || !t) return;
if (s->val == t->val) res.push_back(s);
findTinS(s->left, t);
findTinS(s->right, t);
return;
}

bool sameTree(TreeNode* A, TreeNode* B) {
if (!A && !B) return true;
if (!A || !B || A->val != B->val) return false;
return sameTree(A->left, B->left) && sameTree(A->right, B->right);
}

bool isSubtree(TreeNode* s, TreeNode* t) {
if (!s && !t) return true;
findTinS(s, t);
if (res.empty()) return false;

//second trap: for every root(t) in s, return true as long as one has the same structure with t
vector<bool> allRes;
for (auto node : res) allRes.push_back(sameTree(node->left, t->left) && sameTree(node->right, t->right));

for(auto i : allRes) {if (i) return i;}
return false;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.