Determine if One Binary Tree is a Subtree of Another

You are given two binary trees A and B represented in level order as comma separated strings. Your task is to determine whether tree B is a subtree of tree A.

A subtree of a binary tree A is a tree B that consists of a node in A and all of this node's descendants. The subtree corresponding to the root of A is the entire tree A.

In formal terms, if we denote the tree structure with nodes, you need to check whether there exists a node in A such that the subtree rooted at that node is identical to B. Note that by definition if B is None (empty), it is considered a subtree of any tree A (including when A is also empty). Conversely, a non-empty tree cannot be a subtree of an empty tree.

In mathematical notation, let \(T_A\) and \(T_B\) be two trees, then \(T_B\) is a subtree of \(T_A\) if \(\exists\) a node \(n\) in \(T_A\) such that the structure and node values of the subtree rooted at \(n\) equal \(T_B\). Formally, using the recursive predicate \(\text{isSameTree}(A, B)\):

[ \text{isSameTree}(A, B) = \begin{cases} \text{True} & \text{if } A = B = \text{null}\ \text{False} & \text{if one of } A \text{ or } B \text{ is null}\ (A.val = B.val) \land \text{isSameTree}(A.left, B.left) \land \text{isSameTree}(A.right, B.right) & \text{otherwise} \end{cases} ]

Your program will read the serialized trees from the standard input and output a single line: True if B is a subtree of A, otherwise False.

inputFormat

The input consists of two lines:

1. The first line is a comma-separated list representing the level order traversal of tree A. Use null to denote an empty node.
2. The second line is a comma-separated list representing the level order traversal of tree B (or null if the tree is empty).

Example:

3,4,5,1,2
4,1,2

outputFormat

Output a single line: True if tree B is a subtree of tree A, and False otherwise.

## sample

3,4,5,1,2
4,1,2

True