# 572. Subtree of Another Tree

Reference: LeetCode
Difficulty: Easy

## Problem

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example:

## Analysis

### Recursion (Node Comparison)

We can extract the recursive structure as follows:

isSubtree(s, t):

• The base case is:
• If s == null && t == null, then return true.
• If s == null || t == null, then return false.
• If isSame(s, t) is true, then return true.
• If isSubtree(s.left, t) or isSubtree(s.right, t) is true, then return true.

Time: $O(m \times n)$

• $O(m)$: Every node in s is traversed once.
• $O(n)$: Do isSame(s, t) for each node in t, which traverses at most $n$ nodes in t.

Space: $O(h_s)$ where $h_s$ is the height of s.

### Preorder Sequence

We can find the preorder traversal of the tree s and t, and compare the preorder sequence. If the sequence $S_t$ is a substring of $S_s$, t is a subtree of s.

Also, in order to use this method, we need to treat children of leaf nodes as null value, and other values should have a prior # character to distinguish numbers such as 3 and 23.

Without StringBuilder (13 ms):

Use StringBuilder (5 ms):

Note:

• $m$ is the number of nodes in tree s; $n$ is the number of nodes in tree t.
• String concatenation takes $O(k)$ for a k-length string. Using StringBuilder reduces the time complexity to $O(1)$.

Time: Original: $O(m^2 + n^2 + m \times n)$; Use StringBuilder: $O(m + n)$

• indexOf takes $O(m \times n)$, or $O(m + n)$ with KMP algorithm.

Space: $O(\max{(m, n)})$ because of strings.

Comment
Junhao Wang
a software engineering cat