Blind 75 · #28 · Trees

Subtree of Another Tree

EasyTree matchingTime O(m · n)Space O(h)

Subtree of Another Tree is an easy Trees problem from the Blind 75. The key pattern is tree matching, and a good solution runs in O(m · n) time.

Problem

Determine whether the second level-order tree occurs as an exact subtree of the first.

Input

{"root":[3,4,5,1,2],"sub":[4,1,2]}

Output

true

Input

{"root":[6,2,9,1,3,null,null,null,null,0],"sub":[2,1,3]}

Output

false

Input

{"root":[1],"sub":[1]}

Output

true

At every node of the larger tree, check whether the tree starting there is identical to the smaller one.

Serialising both trees with null markers and searching for one string inside the other gives a linear-time variant.