dsa · easy

Subtree of Another Tree

Return whether sub_root is a **subtree** of root: some node in root is the root of a region that has the same shape and the same values as the whole of sub_root.

Arguments

• root — the larger tree, nested [val, left, right] or None
• sub_root — candidate subtree in the same encoding

Each tree is nested [val, left, right] or None. An empty sub_root is a subtree of every tree. An empty root only matches an empty sub_root.

Example

root = [3, [4, [1, None, None], [2, None, None]], [5, None, None]], sub_root = [4, [1, None, None], [2, None, None]].

The left child of 3 is exactly sub_root, so the answer is true.

If that 2 in root grew an extra left child 0, the shapes would no longer match and the answer would be false.

Constraints

Number of nodes in [1, 2000] for each tree -10^4 <= val <= 10^4 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[3, [4, [1, None, None], [2, None, None]], [5, None, None]]
[4, [1, None, None], [2, None, None]]

Expected:
true

Example 2

Input:
[3, [4, [1, None, None], [2, [0, None, None], None]], [5, None, None]]
[4, [1, None, None], [2, None, None]]

Expected:
false

Open in the Dojo editor