# Leetcode 572 Solution

https://leetcode.com/problems/subtree-of-another-tree

## Solution

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
bool ans;
public:
bool isSameTree(TreeNode* s, TreeNode* t) {
if (s == NULL && t == NULL)
return true;

if (s == NULL || t == NULL)
return false;

return s->val == t->val && isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
}

int getTreeSum(TreeNode* t) {
if (t == NULL)
return 0;

return (t->val + getTreeSum(t->left) * 2 + getTreeSum(t->right) * 3) % 15487039;
}

int traverseTree(TreeNode* s, TreeNode* t, int sum) {
if (s == NULL || ans)
return 0;

int res = (s->val + traverseTree(s->left, t, sum) * 2 + traverseTree(s->right, t, sum) * 3) % 15487039;

if (res == sum && isSameTree(s, t))
ans = true;

return res;
}

bool isSubtree(TreeNode* s, TreeNode* t) {
ans = false;
traverseTree(s, t, getTreeSum(t));
return ans;
}
};
``````