# Straight forward solution

• ``````class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(s == nullptr && t == nullptr) return true;
if(t == nullptr) return true;
if(s == nullptr) return false;

return sameTree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}

bool sameTree(TreeNode* s, TreeNode* t){
if(s == nullptr && t == nullptr) return true;
if(s == nullptr || t == nullptr) return false;
if(s->val != t->val) return false;

return sameTree(s->left, t->left) && sameTree(s->right, t->right);
}

};``````

• The same idea

``````class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
return helper(s,t) || ((s)?isSubtree(s->left,t) || isSubtree(s->right,t):false);
}

bool helper(TreeNode* s, TreeNode* t) {
if (s && t && s->val == t->val) {
return helper(s->left, t->left) && helper(s->right, t->right);
} else if (s == NULL && t == NULL) {
return true;
}
return false;
}

};
``````

• Can anyone tell me the time Complexity of this Code ?
I am thinking it as O(n2) because both the functions are traversing the tree.
And also how to compute time complexity of this kind of recursive functions ?

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