I have question on whether my analysis of runtime and space for algorithm that determine whether a tree S contains a subtree that is exactly the same tree as other tree T My code is as follows:
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null) return subRoot == null;
return isSameTree(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
}
public boolean isSameTree(TreeNode root, TreeNode subRoot) {
if(root == null) return subRoot == null;
if(subRoot == null) return false;
return root.val == subRoot.val &&
isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
}
}
I think the time is O(S * min(S, T)) where S and T are total number of node of tree s and t respectively, and space is O(max(S, T)). I got the time because we are performing dfs on every node of tree s to determine whether it is the same as tree t, and each dfs takes minimum of node of s and t, and space is because our recursion call stack can at most contain minimum of two tree's node, if smaller tree hits null case while dfsing with larger tree, we will just return