# Subtree

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

**Example**

T2 is a subtree of T1 in the following case:

```
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4
```

T2 isnâ€™t a subtree of T1 in the following case:

```
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4
```

## Solution

We can use an recursive algorithm to solve this problem, as shown in the code below. Essentially we are checking every node of T1 against T2. Let m = the number of nodes in T1, and n = the number of nodes in T2, the time complexity of this algorithm is O(mn).