Subtree of Another Tree


Why does inorder traversal work? For the following two trees, the inorder traversal string form will be:
[4,1,null,null,2] => lnull 1 lnull 2 rnull 4 rnull [1,null,4,2] => lnull 1 lnull 2 rnull 4 rnull
As you can see, the serialized form of inorder traversal gives the same value even though the trees are different. I believe it has to be preorder or postorder


@biss said in Subtree of Another Tree:
I do not think the approach one is O(n + m). Is the .contanin(String) function implemented by KMP?
"contanin"? You mean "contains"? Note that that's
HashSet::contains
, notString::contains
. Wouldn't make sense to use KMP there.


@sharma.karan9341 You can add a special character like '#' before every value like I have added in Approach #2.

@vinod23 yes I did that, my approach was a little different but the basic idea was same. But still it would fail because "2#" will be a substring of "12#". But I figured out a way, thanks though.

@sharma.karan9341 We have to add # before each value not after. Now can you give some example on which it fails?


Can be done in O(n+m) by doing inorder and preorder traversals of both the tree and storing them in separate vectors. Let spre and sin be the preorder and inorder vector of s, and let tpre and tin be the preorder and inorder vector for t .
Now after doing this we just need to check if tpre is a subarray of spre, and tin is a subarray of sin, which can be easily checked by doing Something similar to KMP(String) in O(n).
This solution will provide the correct answer because inorder and preorder Traversal are sufficient to reconstruct a tree again. :D