Problem statement

https://binarysearch.com/problems/Find-a-Linked-List-in-a-Binary-Tree/

Solution

The idea is to extend kmp algorithm for trees here! First, let us evaluate prefix function, which we keep in f. Then we traverse tree and do similar logic as we do in kmp.

Complexity

It is O(n + m) for time and space.

Code

class Solution:
    def solve(self, root, h):
        A = []
        while h:
            A += [h.val]
            h = h.next
        
        n = len(A)
        f = [-1] * (n + 1)
        for i in range(1, n + 1):
            f[i] = f[i - 1] + 1
            while f[i] > 0 and A[i - 1] != A[f[i] - 1]:
                f[i] = f[f[i] - 1] + 1

        def dfs(r, i):
            if i >= n: return True
            if not r: return False
            i += 1
            while i > 0 and r.val != A[i - 1]:
                i = f[i - 1] + 1
            return dfs(r.left, i) or dfs(r.right, i)

        return dfs(root, 0)