progress

~/problems / Trees / Binary trees

Subtree of Another Tree

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

TreeNode(val, left=None, right=None) is in the starter. Keep it.

Write contains_copy(big, small) -> bool: True when some node of big, together with everything below it, is an exact copy of small (same shape, same values). Extra nodes underneath don't count as a copy. big itself counts as one of its own subtrees.

#   big:     3          small:   4
#           / \                 / \
#          4   5               1   2
#         / \
#        1   2
contains_copy(big, small)    # True

#   big2:    3
#           / \
#          4   5
#         / \
#        1   2
#           /
#          0
contains_copy(big2, small)   # False: under 4 there is an extra 0

big has up to 2,000 nodes, small up to 200; values repeat often. Aim for O(n·m).

Show hint

Write a helper that says whether two trees are identical, then try it at every node of big.

Topic: Binary trees. Recursive return values (height, best path), BFS by level, BST invariants.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc