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
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.