Your question is Subtree of a Binary Tree. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
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.
Implement is_subtree(root, sub_root).
None.sub_root is an exact subtree of root.def is_subtree(root, sub_root):