Start learning free

LESSON 414 OF 536 · BINARY TREES

Same Tree in Python: Recursive Comparison

Practice O(n) Read the full explanation

Given the roots of two binary trees, p and q, return True if they are the same tree, and False otherwise.

Two binary trees are the same when they have exactly the same shape and every node holds the same value as the node in the same place in the other tree. Two empty trees are the same.

The trees below are written in level order (top to bottom, left to right), with None for a missing child.

 

Example 1:

     p          q
     1          1
    / \        / \
   2   3      2   3

Input: p = [1,2,3], q = [1,2,3]
Output: True
Explanation: Both trees have the root 1, with 2 as its left child and 3 as its right child.

Example 2:

     p          q
     1          1
    /            \
   2              2

Input: p = [1,2], q = [1,None,2]
Output: False
Explanation: The trees hold the same values, but the 2 is the left child of the root in p and the right child in q.

Example 3:

     p          q
     1          1
    / \        / \
   2   1      1   2

Input: p = [1,2,1], q = [1,1,2]
Output: False
Explanation: The shapes match, but the left children hold different values: 2 in p and 1 in q.

 

Constraints:

  • The number of nodes in each tree is in the range [0, 104].
  • Each node value is between -104 and 104.
  • Each tree is at most 400 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, comparing each pair of nodes at most once.

STEP 1 OF 4
    Ctrl + Enter to check

    PYTHON · BINARY TREES

    Same Tree in Python, explained

    Problem overview

    The method isSameTree(p, q) receives the roots of two binary trees and returns True when they are the same tree: exactly the same shape, with the same value in every position. Two empty trees are the same. The lesson provides the TreeNode class, with val, left and right, as shown in a comment in the starter code.

    The trees [1, 2, 3] and [1, 2, 3] are the same. The trees [1, 2] and [1, None, 2] hold the same values, but the 2 is a left child in one and a right child in the other, so they differ. The trees [1, 2, 1] and [1, 1, 2] have the same shape but different values in the left child (2 against 1).

    Approach: compare the roots, then the subtrees

    Two trees are the same exactly when their roots hold the same value, their left subtrees are the same, and their right subtrees are the same. Each of the two subtree questions is the original question on smaller trees, so recursion fits. Before comparing values, the code has to handle missing nodes, since None has no value to read:

    • Both nodes are missing: the trees are the same there.
    • Exactly one is missing: the shapes differ.
    • Both exist: compare their values, then recurse into the children.

    Each pair of nodes is compared at most once, so the time is O(n), where n is the number of nodes in the smaller tree.

    Step by step

    1. Both empty. If not p and not q, return True. not p is true when p is None. This case also ends the recursion when both trees run out at the same moment below a leaf.
    2. Only one empty. If not p or not q, return False. The first test already handled both being empty, so exactly one is empty here.
    3. Different values. If p.val != q.val, return False. Both nodes exist at this point, so reading .val is safe.
    4. Compare the subtrees. Return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right). The roots match, so the trees are the same exactly when both pairs of subtrees are.

    The solution in Python

    class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

    Python details:

    • Truthiness of nodes. A TreeNode object is truthy and None is falsy, so not p works as "p is missing". It would be wrong for a node's value: a node holding 0 is still a node, and the code only applies not to the nodes, never to p.val.
    • != compares values. p.val != q.val compares the numbers. Comparing the nodes themselves with == would not do what this problem needs, because by default two different node objects are never equal, even with identical contents.
    • Short-circuit and. If the left pair differs, the right pair is skipped.
    • Recursion depth. Each tree is at most 400 levels deep, well below Python's default limit of about 1,000 nested calls.

    Complexity

    The time is O(n), where n is the number of nodes in the smaller tree: the recursion stops at the first pair that differs, and when the trees are the same it visits every pair once. The space is the call stack, O(h) for height h.

    Edge cases and common mistakes

    • Two empty trees. [] and [] are the same, and the answer is True.
    • One empty tree. [] against [1], or [1] against [], is False.
    • Same values, different shape. [1, 2] against [1, None, 2] is False. A check that compares only the values in some traversal order, without recording the missing children, would miss this.
    • Reading .val too early. If the value comparison comes before the missing-node checks, it fails with an AttributeError when a node is None.
    • Zero as a value. [0] against [0, None] is True: a node holding 0 is a real node, and an explicit None child is the same as no child.

    Testing

    pqresult
    [1, 2, 3][1, 2, 3]True
    [1, 2][1, None, 2]False
    [1, 2, 1][1, 1, 2]False
    [][]True
    [][1]False
    [1, 2, 3][1, 2, 4]False
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free