Subtree of Another Tree


  • 0

    Click here to see the full article post


  • 3

    Why does in-order traversal work? For the following two trees, the in-order 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 in-order traversal gives the same value even though the trees are different. I believe it has to be pre-order or post-order


  • 0

    @yangshun Thanks for your suggestions. I've updated the approach now.


  • 0
    B

    I do not think the approach one is O(n + m). Is the .contanin(String) function implemented by KMP?


  • 0
    This post is deleted!

  • 0

    @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, not String::contains. Wouldn't make sense to use KMP there.


  • 0
    Y
    This post is deleted!

  • 1

    The first solution is neither O(m+n) time nor O(n) space.


  • 1
    F

    It would be nice to keep consistent what n refers to in complexity analysis. Take first approach for example, it is very confusing n refers to the number of nodes in time complexity, while it refers to the number of subtree in space complexity.


  • 0

    @feng.wen.503 I have updated the complexity. Is it fine now?. Please let me know. Thanks


  • 0
    T

    The first solution also can not use InOrder Traversal?


  • 0

    @Todoloki Now it is preorder traversal. Thanks.


  • 0
    S

    I used the preorder technique but it fails for a test case [12] , [2].


  • 0

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


  • 0
    S

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


  • 0

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


  • 0

    A typo in Approach #1
    At last, we also find the preorder traversal of the given tree t, and check if the same value already exists in the set. If so, the tree s is a subtree of t, otherwise not.
    should be
    If so, the tree t is a subtree of s, otherwise not.


  • 0

    @cloud.runner Thanks. Updated.


  • 0
    V

    Can you explain the time complexity of the first approach? O(m^2+n^2+m*n)
    Why are m and n squared?


  • 0
    N

    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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.