# 19ms C++ solution beats 99.9%

• Two trees are identical when they are recursively identical. Brute force solution would be recursively compare each node in s with t to check for identical. Better solution is to only compare nodes in `s` with the same max depth as `t`. First get max depth of `t`, then recursively check each node in `s`, if depth equals, push to a vector. Then compare each node in the vector with `t`.

``````class Solution {
vector<TreeNode*> nodes;

public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (!s && !t) return true;
if (!s || !t) return false;

getDepth(s, getDepth(t, -1));

for (TreeNode* n: nodes)
if (identical(n, t))
return true;

return false;
}

int getDepth(TreeNode* r, int d) {
if (!r)
return -1;

int depth = max(getDepth(r->left, d), getDepth(r->right, d)) + 1;

// Check if depth equals required value
// Require depth is -1 for tree t (only return the depth, no push)
if (depth == d)
nodes.push_back(r);

return depth;
}

bool identical(TreeNode* a, TreeNode* b) {
if (!a && !b) return true;
if (!a || !b || a->val != b->val) return false;

return identical(a->left, b->left) && identical(a->right, b->right);
}
};
``````

• Nice optimization! One more function, but much faster.

• This is a clever&simple implement.

• @vicch7 Very clever solution! I have a thought, that might improve a little bit of speed. Inside getDepth subroutine before doing nodes.push_back(r) your are checking "if (depth == d)", if you manage to add another condition as in "if (depth == d && r->val == t->val)" the node which doesn't match with the root value of t is not pushed to nodes vector.

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