1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I don't think you need a recurrence, it's O(nm). (In the worst case, you're visiting m nodes for each node in the n-nodes tree). The space complexity is O(max(n,m)) (or the log if you know the trees are balanced, however, it's the maximum you need to take, not the minimum).

PS: one can also have an O(n) test, see for instance https://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/ .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.