Given two binary trees, check whether one is a subtree of another one. This is my algorithm. Basically, it says:
For two binary trees A and B, A is a subtree of B if they are the same tree. If they are not the same tree, then check whether A is a subtree of B.left or a subtree of B.right.
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null || t == null) {
return false;
}
if (sameTree(s, t)) {
return true;
} else {
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
}
public boolean sameTree(TreeNode A, TreeNode B) {
if (A == null && B == null) {
return true;
}
if ((A == null && B != null) || (A != null && B == null)) {
return false;
}
return A.val == B.val && sameTree(A.left, B.left) && sameTree(A.right, B.right);
}
This algorithm works; but my head hurts when I try to analyze the space + time complexity.
For time complexity, I made the following recurrence:
Let n = nodes in B (the bigger tree), and m = nodes in A (the smaller tree)
T(n,m) = min(m, n) + 2 * T(n/2, m)
The logic for the above is that "sameTree" will always fully traverse the smaller of its two arguments. And we only recurse on n, so only that one gets halved in the recursive call.
However, I do not know how to resolve the recurrence. Does anyone have any ideas?
Also, what is the space complexity? I argue it is, in the worst case, the minimum of n and m and, in the best case, the logarithm base two of their minimum (assuming the tree is relatively balanced). These are due to the stack of the recursive calls.
