Subtree of a Binary Tree

HardPython

Problem

Sage software may represent hierarchical structures such as account or reporting trees. Given two binary trees, determine whether the second tree appears as an exact subtree of the first.

A tree is encoded as either None for an empty tree or [value, left, right], where left and right use the same format. A subtree must match both node values and structure, including empty-child positions. Return True if sub_root occurs in root, otherwise return False.

Because the trees can contain many repeated values, avoid relying only on value sequences. Serialize null children explicitly, then use an efficient pattern-matching algorithm to search for the serialized sub_root inside the serialized root.

Formal Specification

Implement is_subtree(root, sub_root).

Input: Two binary trees represented as nested lists or None.
Output: A Boolean indicating whether sub_root is an exact subtree of root.
Values are integers and may be negative or repeated.

Constraints

0 <= number of nodes in either tree <= 100000
-10^9 <= each node value <= 10^9
Values may repeat
Every tree is represented as [value, left, right] or None
An empty sub_root is considered a subtree of any root

Function Signature

def is_subtree(root, sub_root):

Sage software may represent hierarchical structures such as account or reporting trees. Given two binary trees, determine whether the second tree appears as an exact subtree of the first.

Formal Specification

Implement is_subtree(root, sub_root).

Input: Two binary trees represented as nested lists or None.
Output: A Boolean indicating whether sub_root is an exact subtree of root.
Values are integers and may be negative or repeated.