Efficient ways to check if two binary trees are the same

Question

I implemented a recursive solution in Python to check if two binary trees are identical, which traverses nodes recursively and compares values and structure. The time complexity is O(n), space O(h).

Here is my code:

class TreeNode:
    def __init__(self, key=None, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    if p is None and q is None:
        return True #just if both are empty

    #if both are not empty and nodes dont match, recur the left and right subtree
    return (p is not None and q is not None) and (p.key == q.key) and \
        isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

p = TreeNode(1)
q = TreeNode(1)

print(isSameTree(p, q))

Is there a faster algorithm? Is there a way to optimize memory usage? Is there an iterative alternative that is more practical?

Questions about improving otherwise working code may be better suited for Code Review, but be sure to follow their content guidelines and How to Ask to ensure an on-topic question. — jmoerdyk
– jmoerdyk, Commented Sep 18 at 19:12
@jmoerdyk thank u for the suggestion, i will check Code review and make sure to follow their guidelines next time. — Jared McCarthy
– Jared McCarthy, Commented Sep 18 at 20:11
Your code is correct but the comment #if both are not empty and nodes dont match, recur the left and right subtree is wrong — Stef
– Stef, Commented Sep 23 at 12:47

greybeard · Accepted Answer · 2025-09-29 12:14:16Z

Without additional information, there is no algorithm that can avoid comparing each and every pair of keys.
Defining a TreeNode.__eq__() may or may not be useful.

Micro optimisation: Don't check for both None:

def same_trees(p: TreeNode, q: TreeNode) -> bool:
    """ Establish whether trees rooted in p and q have 
         equal keys and the same structure.
    """
    if p is q:
        return True
    if p is None or q is None or p.key != q.key:
        return False
    #
    return same_trees(p.left, q.left) and same_trees(p.right, q.right)

One could "iterate" half the descends - who would?

def same_trees(p: TreeNode, q: TreeNode) -> bool:
     """ Establish whether trees rooted in p and q have
          equal keys and the same structure.
     """
     while p is not None and q is not None:
         if p.key != q.key or !same_trees(p.right, q.right):
             return False
         # p, q = p.left, q.left  # when bothered about recursive calls
         p = p.left               # avoid temporary tuples
         q = q.left
     return p is q

(reduces call depth(→stack space) where the path to the deepest node is not all right children.)

Xellos · Accepted Answer · 2025-09-29 10:29:54Z

1

If you're fine with a small (arbitrarily small) chance of failing, you can use hashing. Assign a unique value to each node, where value(v) = f(value(v.left), value(v.right), v.key). Two subtrees are identical iff the values in their roots are identical.

Beside a chance of giving false positives, this is slow to recompute if anything changes - but any check for identity is very fast.

If you use multiple sufficiently distinct functions f to store multiple hash values, you can check if two tuples of values are identical to exponentially decrease the chance of failing.

You shouldn't concern yourself with memory complexity. The tree itself will consume at least a comparable amount of memory to your recursion's call stack or to also storing hashes.

answered Sep 29 at 10:29

Xellos

7522 silver badges11 bronze badges

6 Comments

greybeard Sep 29 at 12:15

Why would computing a hash value be preferrable to checking equality?

Xellos Sep 29 at 12:36

I don't understand what you mean, these aren't two competing alternatives. The OP question is for a way to check equality of any two subtrees. When you compute hashes, you can do that in constant time - it's an algorithm that solves the problem of checking equality. It's an alternative to brute force traversal. As to why it's better: there can be much more pairs to check than there are nodes in the tree. Even when brute force has many common termination conditions to speed it up, simply comparing a pair (or multiple pairs) of numbers has better performance.

greybeard Sep 29 at 17:03

I don't read that way. Their explict questions are faster algorithm? less memory usage? more practical iterative alternative? "When you compute hashes[→O(1)]" When you keep summary information: O(n) additional space, even when not establishing equality.

Xellos Sep 29 at 18:12

Tradeoffs exist, that's something you just have to accept. There won't always be an algorithm that can answer a query faster & has no precomputation & uses less additional space. See the last paragraph of my answer. O(n) + O(n) = O(n). If space is so much of a problem that a constant factor on O(n) matters, the question shouldn't be for Python in the first place.

greybeard Sep 29 at 17:04

"As to why it's better: there can be much more pairs to check than there are nodes in the tree." No, not where equality is defined to include structural equality.

Xellos Sep 29 at 18:13

False. "Is the subtree of node i equal to the subtree of node j?" There are n(n-1)/2 unordered pairs (i,j) but only n nodes.

trincot · Accepted Answer · 2025-10-10 18:14:04Z

Is there an iterative alternative that is more practical?

What is "practical" will be a matter of opinion, but sure there is an iterative alternative: you'd maintain a stack or queue to keep track of which nodes/subtrees still need to be visited.

You could also create an iterator that traverses one binary tree in a way that its shape is uniquely defined by it: have it yield None for every lacking left or right child.

For instance:

def iter_tree(p: TreeNode):
    stack = [p]
    while stack:
        node = stack.pop()
        yield node
        if node:
            stack.extend((node.right, node.left))


def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    return all(a == b or a and b and a.key == b.key
               for a, b in zip(*map(iter_tree, (p, q))))

Collectives™ on Stack Overflow

Efficient ways to check if two binary trees are the same

3 Answers 3

Comments

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related