Leetcode 0572 Subtree of Another Tree

Problem statement

https://leetcode.com/problems/subtree-of-another-tree/

Solution 1

First approach is straightforward: just try all nodes and and start to compare trees.

Complexity

Time complexity is O(mn), where m and n are number of nodes in each tree.

Code

class Solution:
    def isSubtree(self, s, t):
        def equal(x, y):
            if not x and not y: return True
            if not x or  not y: return False
            return x.val == y.val and equal(x.left,y. left) and equal(x.right, y.right)
        
        def traverse(x, y):
            if not x: return False
            return equal(x,y) or traverse(x.left,y) or traverse(x.right,y)
        
        return traverse(s,t)

Solution 2

There is also very nice solution using preorder traversal to string. What we need to do is to construct string from both trees and then check if one is substring of another, which can be done in O(m+n), using KMP. Be careful when we construct string representation: we need to add one extra : before we find one string in another: we need this to avoid cases when 1 is subtree of 12 (we do not need it to add it to the end, because end will always be #.

Complexity

Time and space complexity will be O(m+n).

Code

class Solution:
    def isSubtree(self, s, t):
        def dfs(root):
            if not root: return "#"
            return str(root.val) + ":" + dfs(root.left) + ":" + dfs(root.right)
        return ":" + dfs(t) in ":" + dfs(s)