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