Subtree

Python data engineering interview problem. Difficulty: advanced. Pattern: Trees. About 18 minutes. Part of the Pro drill bank.

Whether sub is a subtree of root (level-order inputs). Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A hierarchy may contain a smaller hierarchy inside it, such as a service group inside a larger organization. The smaller tree must match at 1 node and below it. Return whether sub appears as a complete subtree of root, including values and missing-child structure. Write is_subtree(root: list, sub: list) -> bool. The node 4 in [3, 4, 5, 1, 2] has children 1 and 2, matching [4, 1, 2], so the result is True. The starter file already has the function name and harness print lines. Keep them and fill only the function body.

Requirements

• Try each possible root node.
• Compare the whole candidate subtree, not only its root value.
• Return false when no complete match exists.

Constraints

• Inputs are level-order tree representations with possible None values.
• The return type is bool.

Examples

Input: is_subtree([3, 4, 5, 1, 2], [4, 1, 2]) Output: True Left subtree matches.

Topics: lakebench, python, subtree, dfs.

More Python interview questions · All interview problems · Learn data engineering