# Problem Statement

From: https://leetcode.com/problems/subtree-of-another-tree/solution/

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

Given tree s:

` 3`

/ \

4 5

/ \

1 2

Given tree t:

` 4 `

/ \

1 2

Return **true**, because t has the same structure and node values with a subtree of s.

**Example 2:**

Given tree s:

` 3`

/ \

4 5

/ \

1 2

/

0

Given tree t:

` 4`

/ \

1 2

Return **false**.

# Proof

# Solution

## The Code

## How to think of this problem

- When you see that the problem is related to trees, you must immediately ask yourself — can I use a DFS tree traversal algorithm? Namely: preorder, in-order, and postorder traversal.
- Since we need to check if a tree is a subtree, we are always checking the root of the subtree first. This is exactly what preorder traversals do, they process the root first, and then continuing traversing down the left/right subtrees.
- Once we’ve decided to use preorder, we have to consider the edges cases. What if the parent is null, or the subtree is null? We add if statements to handle these cases.
- Now we create two functions: isSubtree() our main function, and isSame() a helper.

**equals()**

- Returns true if two nodes have the same value, and the same children.