Free Trees lessonsTrees · Stage 4 · Building and comparing · Step 3

Is one tree inside another

Decide whether a small tree appears exactly as a subtree of a bigger one, by trying the comparison at every node of the bigger tree. About 14 minutes.

Try the match at every node

A tree is a subtree of another if some node of the bigger tree has exactly the same shape and values below it as the small tree. You already know how to check whether two trees are identical.

So run that check at the root of the big tree. If it fails, ask the same question about its left subtree, and its right subtree. If any of the three succeeds, the answer is yes.

Same tree here? check at the current node.

Else look below: left subtree, then right.

In code

def size(root):
    if not root:
        return 0
    left = size(root.left)
right = size(root.right)
return 1 + left + right

Is the tree 4, 4, 6 inside the tree 5, 4, 4, 1, 3, 4, 6?

match: no

At the root 5: the small tree starts with 4, so they differ at once. Try the left subtree.

Move 1 of 4

The base cases

An empty small tree is considered to be inside every tree, so answer yes. If the small tree is not empty but the big tree has run out of nodes, there is nowhere left to match, so answer no.

The identical-trees check needs its own base cases. Two empty trees are identical. If only one is empty, they differ. Otherwise the values must be equal, and both pairs of children must be identical.

Empty small tree: is inside everything.

Match the whole subtree, not just the root value.

In code

if sub is None:
    return True      # nothing left to match
if root is None:
    return False     # ran out of tree

Quick check

The small tree has a single node, 2. The big tree has a 2 somewhere, with children below it. Is the small tree inside?

ANo, because that 2 has children the small tree does not
BYes, because a 2 appears
CYes, if the value 2 is a leaf somewhere else

Show the answer

No, because that 2 has children the small tree does not. A subtree must match all of the descendants of its top node, not just the top.

Your problem

Subtree of another tree

Given the roots of two binary trees root and subRoot, return true if there is a node in root whose subtree has exactly the same structure and node values as subRoot. A subtree of a tree consists of a node and all of that node's descendants. An empty subRoot is a subtree of every tree.

Example

root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2] → true

0 ≤ number of nodes in each tree ≤ 2,000 · -10,000 ≤ node.val ≤ 10,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.