Subtree of Another Tree

Easy

treerecursiondfs

Given the roots of trees root and subRoot, return true if some node of root (together with all its descendants) is structurally identical to subRoot, with equal values.

Input

Line 1: level-order tokens for root (null = missing child)
Line 2: level-order tokens for subRoot

Output: true or false.

Example 1

Input:

3 4 5 1 2
4 1 2

Output:

true

Example 2

Input:

3 4 5 1 2 null null null null 0
4 1 2

Output:

false

The candidate subtree at 4 has an extra node 0 under 2.

Constraints

1 ≤ root nodes ≤ 2000, 1 ≤ subRoot nodes ≤ 1000
-10^4 ≤ values ≤ 10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Subtree of Another Tree

Easy

treerecursiondfs

Given the roots of trees root and subRoot, return true if some node of root (together with all its descendants) is structurally identical to subRoot, with equal values.

Input

Line 1: level-order tokens for root (null = missing child)
Line 2: level-order tokens for subRoot

Output: true or false.

Example 1

Input:

3 4 5 1 2
4 1 2

Output:

true

Example 2

Input:

3 4 5 1 2 null null null null 0
4 1 2

Output:

false

The candidate subtree at 4 has an extra node 0 under 2.

Constraints

1 ≤ root nodes ≤ 2000, 1 ≤ subRoot nodes ≤ 1000
-10^4 ≤ values ≤ 10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.