Same tree and subtree checks in Python

Why this lesson matters

Two trees can hold the same values and still be different. A family tree with the same names in the wrong branches describes a different family. A folder with the same files in another folder is a different folder. Programs ask these questions too: are these two trees identical, and does this small tree appear somewhere inside that large one?

This lesson builds two checks. The first, is_same_tree, asks whether two trees have the same shape and the same value at every position. The second, is_subtree, asks whether a small tree appears as a complete branch of a bigger tree. Both are short recursive functions. Both depend on the None-child idea from the first lesson of this module: a missing child is None, and None means there is no node at that position.

To follow along, you need to know how to write a recursive function, which means a function that calls itself on smaller pieces of its input. The code below defines its own TreeNode class so each program runs on its own.

What "the same" means

Two binary trees are the same when they have the same shape and the same value at every matching position. The word that matters is position. A position is the path from the root: go left, go right, go left again, and so on. Two trees can hold equal values and still differ, because one value sits at a different position.

Here are three trees. Tree A is the starting point. Tree B is A with an extra node, a 0 under the 2. Tree C holds the same five values as A, but the 1 and 2 sit in different places.

Tree A:

        3
       / \
      4   5
     / \
    1   2

Tree B, which is A with a 0 under the 2:

        3
       / \
      4   5
     / \
    1   2
       /
      0

Tree C, which holds the values 3, 4, 5, 1 and 2 but in different places:

        3
       / \
      4   5
     /
    1
     \
      2

Tree A and tree C look similar at a glance, because both contain the same numbers. In A, the 2 is the right child of 4. In C, the 2 is the right child of 1, which is the left child of 4. The shape is different, so the trees are different. A plain list of values cannot tell them apart, so the check has to look at the links between nodes.

Base cases first

A recursive check starts with the simplest situations, called base cases, and then handles the general case by asking the same question about the children. For two nodes p and q, there are four situations to handle.

1. Both are None. Both trees are empty at this position, so they match. Return True.
2. Exactly one is None. One tree has a node here and the other does not, so they differ. Return False.
3. Both exist but their values differ. Return False.
4. Both exist and their values match. The trees match only if the left children match and the right children match. Ask the same question for p.left and q.left, and for p.right and q.right.

Case 4 needs both answers to be True. In Python, and evaluates the left side first, and if the left side is False it stops at once without evaluating the right side. This is called short-circuit evaluation. It saves work, and it matters for the mistakes section below.

The code for these four cases is:

def is_same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

The first if is case 1. The second if is case 2. The third if is case 3. The last line is case 4. Notice that the second if runs only when at least one side is None, so p.val is never read when p is None. The order of the first three checks is what keeps the code safe.

Worked example 1: a small trace

Take the two trees d and e below. They differ only in the left child of the root.

d:  1        e:  1
   / \          / \
  2   3        9   3

Trace is_same_tree(d, e). Each line is one call, with the two nodes it compares.

Call 2 returns False to call 1. Because the left side is False, the and stops there. The right children, 3 and 3, are never compared. The final answer is False. The code is correct even though it skipped half the tree, because a single difference is enough to answer "not the same".

Checking whether one tree is inside another

The second question is whether a small tree sub appears somewhere inside a big tree root. Here, "appears" means that some node in root has a branch that is the same as sub, from that node down.

The method is simple to state. Visit every node of root. At each node, call is_same_tree with that node and sub. If any call returns True, the answer is True. If every node has been tried and none matches, the answer is False.

Here is the code:

def is_subtree(root, sub):
    if root is None:
        return False
    if is_same_tree(root, sub):
        return True
    return is_subtree(root.left, sub) or is_subtree(root.right, sub)

The first if handles a root that is None. A None tree has no branches, so it cannot contain sub. The second if asks whether the branch starting at root matches sub. If it does not, the last line tries the left branch and then the right branch. The or stops as soon as one side returns True.

This code assumes that sub is not None. The practice section has an exercise that changes the code so an empty sub counts as a subtree of every tree.

Worked example 2: a subtree that is found

Take the big tree A from earlier and look for this small tree:

    4
   / \
  1   2

Trace is_subtree(A, sub):

1. The root of A is 3. is_same_tree(3, sub) compares 3 with 4 and finds different values. It returns False, so the code moves on.
2. The code calls is_subtree on the left child of A, which is the 4. is_same_tree(4, sub) compares 4 with 4, then the left children 1 and 1, then the right children 2 and 2. Every pair matches, so it returns True.
3. The True travels back up to the top call, which returns True.

The program below builds trees A, B and C and prints the results of these calls. Its output is:

is_same_tree(A, copy of A) = True
is_same_tree(A, B)         = False
is_same_tree(A, C)         = False
is_subtree(A, sub)         = True
is_subtree(B, sub)         = False
is_subtree(C, sub)         = False
is_subtree(None, sub)      = False

Worked example 3: a near match that fails

Tree B has the same 4, 1 and 2 as the small tree, but it has an extra 0 under the 2. Trace is_subtree(B, sub) at the node 4:

1. is_same_tree(4, sub) compares 4 with 4, then 1 with 1. Next it compares 2 with 2, and that pair matches. Then it looks at the children of these two 2 nodes. The 2 in B has a left child, 0, but the 2 in sub has no left child. One side is None and the other is not, so the call returns False.
2. The rest of the search continues at the other nodes of B, such as the 1 and the 5. None of them has the shape of sub, so each returns False.

The answer is False. The check is strict. It does not accept a match that has extra nodes, even if all the values of sub appear in the same order inside root.

How much work the checks do

is_same_tree stops at the first difference. In the best case, it finds a difference near the top and returns quickly. In the worst case, the two trees match in almost every position and the function visits every node of the smaller tree.

is_subtree calls is_same_tree once for each node of root. If root has n nodes and sub has m nodes, the worst case can take about n times m steps. That is slow for large inputs, but it is simple to write and to check. Faster methods exist, but they are outside the scope of this lesson.

Both functions use recursion. Each call adds a frame to the call stack, which is the memory Python uses to remember where each unfinished call is. Python limits how deep that stack can grow, and the default limit is 1000 calls. A tree that is very deep, such as one long chain of 1,000 nodes, can exceed that limit, and Python then raises a RecursionError. The number of nested calls is the height of the tree, so a very tall tree is the case to watch for.

Common mistakes

Mistake 1: using or where and belongs

The check for children must use and, because both children have to match. A version that uses or answers "yes" when only one child matches. Here is that version, run on d and e from worked example 1:

Output:

correct is_same_tree(d, e)  = False
wrong   is_same_tree_or(d, e) = True

The wrong version returns True because the right children, 3 and 3, match. This is a common logic error in tree comparison. Python accepts both versions, so only a test with differing trees shows the problem.

Mistake 2: comparing values with is instead of ==

In Python, == asks whether two values are equal, and is asks whether two names point at the same object. For small whole numbers the two often agree, because CPython (the standard Python program) keeps a shared object for each number from -5 to 256. For larger numbers, two equal values can be two separate objects. A check that uses is then reports a difference between equal values.

Output:

is_same_by_identity(1000, 1000) = False
is_same_by_identity(5, 5)       = True

Both trees hold the value 1000, yet the answer is False. The fix is to compare with !=, which compares the values. The is operator is for checking None, and only for that: p is None is the right form, and p.val is not q.val is the mistake. The result of the mistake depends on how the numbers were created, so it can pass in one test and fail in another.

Mistake 3: reading a field before the None check

If the value comparison comes before the None checks, the program reads an attribute of a None node and fails. Here is that version:

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def is_same_no_none_check(p, q):
    if p.val != q.val:
        return False
    return True
 
 
is_same_no_none_check(None, TreeNode(1))

Calling it with a None first argument prints this error (the file path and caret marks depend on where the file is saved and on the Python version):

Traceback (most recent call last):
  File "main.py", line 14, in <module>
    is_same_no_none_check(None, TreeNode(1))
    ~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^
  File "main.py", line 9, in is_same_no_none_check
    if p.val != q.val:
       ^^^^^
AttributeError: 'NoneType' object has no attribute 'val'

The message tells you what failed. Python could not read the attribute val, because p is None. The File lines show where the call was made and which line failed. The fix is the first if from the base cases: check for None before you touch any attribute.

Mistake 4: comparing two lists of values

A common first idea is to write each tree out as a list, then compare the lists. This fails. Tree A and tree C from earlier both give the list [3, 4, 1, 2, 5] when you read them in preorder, which is the walk that visits the node, then the left subtree, then the right subtree. The lists are equal, but the trees are different. The list does not record where the None children are, so it cannot separate the two shapes. Compare the links, as is_same_tree does, not the flattened values.

Practice

Exercise 1: predict the answer

Are these two trees the same? x is the tree 1 with children 2 and 3. y is the tree 1 with children 3 and 2.

Show the answer

No. The root values match and so do the number of nodes, but the 2 is the left child in x and the right child in y. is_same_tree(x, y) returns False. Before you test, check the position of each value, not only the values.

Exercise 2: compare two trees with a queue

Write is_same_tree without recursion, using a queue. The queue holds pairs of nodes, one from each tree, that are at the same position. Each pair is checked in turn.

Show the answer

from collections import deque
 
 
def is_same_tree_queue(p, q):
    queue = deque([(p, q)])
    while queue:
        a, b = queue.popleft()
        if a is None and b is None:
            continue
        if a is None or b is None:
            return False
        if a.val != b.val:
            return False
        queue.append((a.left, b.left))
        queue.append((a.right, b.right))
    return True

The queue stores pairs, not single nodes, so each item is a tuple, which is a fixed group of two values. A pair whose parts are None is allowed, because the pair itself is not None. Running this on x and y from exercise 1 returns False, and on two equal copies it returns True.

Exercise 3: allow an empty subtree

The is_subtree function in this lesson returns False when sub is None. Change it so that an empty tree counts as a subtree of every tree, including an empty tree.

Show the answer

Add one check at the top of the function:

def is_subtree(root, sub):
    if sub is None:
        return True
    if root is None:
        return False
    if is_same_tree(root, sub):
        return True
    return is_subtree(root.left, sub) or is_subtree(root.right, sub)

With this change, is_subtree(None, None) returns True, and is_subtree(None, sub) for a non-empty sub still returns False. The order of the two checks matters. If the root is None check came first, the empty sub case would return False.

Exercise 4: find the bug in a mirror check

A student wrote this version of is_same_tree and says it compares two trees. Does it?

def mirror_bug(p, q):
    if p is None or q is None:
        return p is q
    return p.val == q.val and mirror_bug(p.left, q.right) and mirror_bug(p.right, q.left)

Show the answer

No. The code compares the left child of p with the right child of q, and the right child of p with the left child of q. That checks whether one tree is the mirror image of the other, not whether the two trees are the same. For x = 1(2, 3) and y = 1(3, 2), the code returns True, but the trees are not the same. The fix is to compare p.left with q.left and p.right with q.right, as in is_same_tree. Mirror checks are covered in the invert, mirror and symmetry lesson of this module.

Exercise 5: a subtree that has the same values but a different shape

Tree B from this lesson contains the same values as sub, plus one extra node 0. Explain, in your own words, why is_subtree(B, sub) returns False even though every value of sub appears in B in the same order.

Show the answer

The check is about shape, not about the set of values. Every node of sub must match a node in the same position in root, and nothing extra can sit under those nodes. The 2 in sub has no children, while the 2 in B has a left child 0. When is_same_tree reaches those two 2 nodes, one side is None and the other side is not, so the match fails. The search then tries every other node of B, and none of them has the shape of sub, so the answer is False.

Summary

• Two trees are the same when every position has the same node or the same None, and the same value at each node.
• Check the base cases first: two None nodes match, one None node does not match, and values must be equal before the children are checked.
• is_subtree tries is_same_tree at every node of the big tree and returns True when any call matches.
• Use and for the two children, because both must match, and check for None before reading any attribute.
• Compare values with == or !=, and use is only to check for None.
• Comparing two flat lists of values cannot detect a difference in shape, so compare the links between nodes.