Complexity of “Subtree of Another Tree”

Question

I wrote an algorithm for a leetcode question. The question asks:

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

My solution for this problem consists of a breadth-first traversal of the first tree s, and a function that checks whether any subtree of s is the same tree as t. The entire solution can be found here.

I am having a tough time figuring out the time and space complexity of this solution.

I understand that the isSame function has a time and space complexity of O(n). (See my explanation below), and the isSubtree function will call isSame for every node in s. However, the size of the input to isSame changes on each call, and I am having a hard time putting both pieces together to get an overall runtime / space complexity.

Explanation of isSame time and space complexity:

For the function that checks whether two trees are the same (isSame), the worst-case time complexity occurs when the trees are indeed equivalent. In this case, we will check every node and do a constant amount of work for each node, and thus our time complexity is O(n), where n is the number of nodes in either tree (they are the same). Furthermore, the function isSame function is recursive, and our time complexity will be linear with the height of the smallest tree. In the worst case, both trees are equivalent, and they have degenerated to a linked list, in which case the number of frames on our call stack will be the same as the height, which is the same as the number of nodes, so that's O(n) for the space complexity.

Answer 1

The time complexity of isSame is not linear in the height of the smallest tree. Think for example of two copies of a complete binary tree (where all nodes have the same value).

That said, the time complexity of isSame is always $O(m)$, where $m$ is the number of vertices in the smallest of the two input subtrees.

Let me assume that the number of vertices $m$ of $t$ is at most the the number of vertices $n$ of $s$ (as otherwise the answer is trivial).

Your algorithm requires time $\Theta(n m) = O(n^2)$ in the worst case. The upper bound is obtained by simply multiplying the number of vertices of $s$ with the $O(m)$ upper bound to the complexity of isSame. The lower bound is obtained, e.g., by letting $s$ be a path on $n$ nodes rooted in one of its endpoints and $t$ be a path on $m$ nodes rooted in one of its endpoints (as before, all vertices have the same value). The first $\lfloor n/2 \rfloor$ invocations of isSame require $\Omega(m)$ time each, for an overall time complexity of $\Omega(n m)$. Notice that this is $\Omega(n^2)$ for $m=\Omega(n)$.