# inorder+preorder traversal + KMP

• Saw many have posted their answers using any two order traversal array(I use preorder and inorder in this example) to decide if one tree is subtree of another.

Just want to add some extra logic here: After generating traversal arrays, we could apply KMP algorithm to determine if one array exists as other array's subarray. The code(Python) is like the following:

``````    ...... (code generates inorder and preorder traversal)
inorder_exist_subarray = self.existIn(inorder_s, inorder_t)
preorder_exist_subarray = self.existIn(preorder_s, preorder_t)
if res1 and res2:
return True
else:
return False
def build_lps(self, arr):
index = 0
i = 1
res = [0]
while i < len(arr):
if arr[i] == arr[index]:
index += 1
res.append(index)
i += 1
else:
if index == 0:
res.append(0)
i += 1
else:
index = res[index-1]
return res
def existIn(self, arr_s, arr_t):
lps_t = self.build_lps(arr_t)
i = 0
j = 0
while i < len(arr_s):
if j == len(arr_t):
return True
if arr_s[i] == arr_t[j]:
i += 1
j += 1
else:
if j == 0:
i += 1
else:
j = lps_t[j-1]
if j == len(arr_t):
return True
return False
``````

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