Two binary trees **T** an **S** and given, the task is identify if "S" is a sub-tree of "T".

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in order.

## Solutions

### Method 1: Recursion

Traverse the tree S in **level-order** fashion.

If current node for T and S are equal, check for their left and right sub-trees, else check if S is present in either left or right sub-trees of T.

For any recurrence is S is exhausted return** "true"** i.e. S is found in T, else if T is exhausted return **"false"** i.e. S could not be found in T.

##### Complexity

The time complexity of this solution is

**O(n*m)**, where "n" is number of nodes in T and "m" is number of nodes in S, and space complexity is**O(n)**due to call stack.