You can use the following algo to check whether tree SMALL is a part of tree LARGE:
- Compute height of smaller tree: small_height = height(SMALL)
- Recurse large tree, computing height in each node
- If node height is the same as small tree height, compare trees:
left_height = recurse(tree.left)
right_height = recurse(tree.right)
height = max(left_height,right_height) + 1
Time analysis is simple: you may visit each node in large tree once or twice - once when computing height and another time when comparing it to small tree. So, browsing large tree is O(n), and computing height of small tree require to visit each node so it's O(m).