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.