Tree is Subtree Check

Problem

Check whether one binary tree is a subtree of another.

tree and sub are level-order lists with None marking missing nodes. sub is a subtree when some node of tree roots a structurally identical tree with the same values.

Return True if sub is a subtree, otherwise False. An empty sub counts as a subtree and an empty tree does not contain a non-empty sub.

Hint

A missing node in sub must line up with a missing node in tree, not match anything.

Test cases

case 1

in: [[1,2,3,4,5],[2,4,5]]

expected: true

case 2

in: [[1,2,3,4,5],[2,4]]

expected: false

case 3

in: [[1,2,3],[1,2,3]]

expected: true

case 4

in: [[1,2,3],[4]]

expected: false

case 5

in: [[1],[1]]

expected: true

Starter codePython

def is_subtree(tree, sub):
    # Your code here
    pass

5 test cases · run your code against them in the editor