Subtree Check in Binary Trees

You are given two binary trees, T and S. Your task is to determine whether tree S is a subtree of tree T, meaning S must match the structure and node values of some subtree in T.

Input:

The first line contains an integer ‘T’, indicating the number of test cases.

Each test case has two subsequent lines:
1. The first line holds the level order traversal of tree T, with node values separated by a space. Replace null nodes with -1.
2. The second line holds the level order traversal of tree S, similarly formatted.

Output:

For each test case, output a single line with 'true' if S is a subtree of T; otherwise, 'false'.

Example:

Input:

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Output:

true

Constraints:

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

Note:

The input format provided above elaborates on how to parse the tree in a single line, substituting null (-1) for non-existent nodes.