Subtree of Another Tree Problem Statement

Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.

Explanation:

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants. The entire tree is a subtree when the subtree corresponds to the root node; otherwise, it's termed a proper subtree.

Input:

The first line of input contains an integer ‘T’ representing the number of test cases. The following lines represent the test cases. Each test case consists of two lines. The first line contains the elements of the first tree in level order, with node values separated by a single space. The second line contains the elements of the second tree in level order, also separated by a single space. Use -1 to denote a null node.

Output:

For each test case, print "true" if tree S is a subtree of tree T; otherwise, print "false". Each result should be on a new line.

Example:

Input:
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Output:
false

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N, M ≤ 1000
• 0 ≤ data ≤ 10⁶ and data ≠ -1

Note: You do not need to print anything; it has already been taken care of.