@giridhar_bhageshpur I think it is not a O(n) solution since spreorder.contains(tpreorder) is not implemented by KMP algorithm in JAVA, so i think it is still O(n^2) time compelxity. Correct me if I am wrong!
Wow really impressed by your merkle tree solution. Genius!
For this problem though, collision resistant hash functions like sha256 are not necessary, from performance perspective. You can use some computationally cheaper hash functions. With an addition of O(|T|) checking every time hash values match, correctness is also made sure.
Is this algorithm passing all tests? looks like this algo will tell true for fragment of tree s matching tree t, but not the subtree itself. In my opinion, to solve this problem, one might have to extend the node class to have an extra field of serialized tree representation. Then compute serialized version of tree t in O(|t|) time. For tree s, populate the serialized field for each node using DFS, which will take O(|s|) time and then search for serialized(t) string by doing a tree traversal O(|s|) time. Hence over all time complexity in that case will be O(|s| + |t|) with same amount of storage complexity.
@vicch7 Very clever solution! I have a thought, that might improve a little bit of speed. Inside getDepth subroutine before doing nodes.push_back(r) your are checking "if (depth == d)", if you manage to add another condition as in "if (depth == d && r->val == t->val)" the node which doesn't match with the root value of t is not pushed to nodes vector.
Although it's O(n^2), but your solution is still faster than mine, which also is O(n^2). I think using string does help in Python. I'm glad that you got a job offer as an algorithm engineer. I can't imagine me learning code for just 10 months can land a job like that.
Can anyone tell me the time Complexity of this Code ?
I am thinking it as O(n2) because both the functions are traversing the tree.
And also how to compute time complexity of this kind of recursive functions ?
@StefanPochmann You are right! I didn't check the complexity of find function. To get a truely linear time algorithm, we have to use KMP in my case here. I already upload the code. Thank you for the question!
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def isSubtree(self, s, t):
:type s: TreeNode
:type t: TreeNode
# check if two trees are the same
def sametree(p, q):
if p and q:
return p.val == q.val and sametree(p.left, q.left) and sametree(p.right, q.right)
return p is q
if s is None:
if sametree(s, t):
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)