Reference: LeetCode

Difficulty: Easy

My Post: [Java] Recursion (Node Comparison) & Preorder Sequence Comparison (StringBuilder)

## 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:**

1 | // s t |

1 | // s t |

## 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
- If
`isSame(s, t)`

is`true`

, then return`true`

. - If
`isSubtree(s.left, t)`

or`isSubtree(s.right, t)`

is`true`

, then return`true`

.

1 | public boolean isSubtree(TreeNode s, TreeNode t) { // takes O(m x n) |

**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`

):

1 | public boolean isSubtree(TreeNode s, TreeNode t) { |

Use `StringBuilder`

(`5 ms`

):

1 | public boolean isSubtree(TreeNode s, TreeNode t) { |

**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.