Check if two binary trees are equal

Question

I've recently solved the LeetCode's "Same Tree" problem:

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

The problem itself and the idea is simple: traverse the tree in a way that preserves the structure - returning None for non-existing left or right sub-tree.

Here is the complete working code:

from itertools import izip


def traverse(node):
    if not node:
        yield None
    else:
        yield node.val
        if node.left:
            for val in traverse(node.left):
                yield val
        else:
            yield None
        if node.right:
            for val in traverse(node.right):
                yield val
        else:
            yield None


class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        try:
            for node_p, node_q in izip(traverse(p), traverse(q)):
                if node_p != node_q:
                    return False
        except StopIteration:
            return True

        return True

It was accepted by the Online Judge, but the code looks a bit lengthy. Is there a way to further simplify or improve the solution? Also, is it the most optimal way to solve the problem?

Note that I cannot use yield from since the OJ is Python 2.7 only.

---

FYI, here is what LeetCode uses as a Tree/Node:

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Answer 1

Since you have a check if not node, can't you just ignore checking if node.left and if node.right? How about:

def traverse(node):
    if not node:
        yield None
    else:
        yield node.val
        for val in traverse(node.left):
            yield val
        for val in traverse(node.right):
            yield val

Also in line for node_p, node_q in izip(traverse(p), traverse(q)) you have misleading variable names, since node_p and node_q aren't actually nodes, but their values.

Was class Solution a requirement? Because it isn't easy to use:

s = Solution()
result = s.isSameTree(root1, root2)

It'd be easier to use a function instead:

result = isSameTree(root1, root2)

Or maybe

result = root1.isSameAs(root2)

And if you want to keep the class then Solution isn't a great name either because you can apply different arguments to it. Checker or Comparator would indicate performed functionality more clearly.

Answer 2

Exit the check early

Basically, you have a recursive traversal operation that traverses the two input trees sort of in parallel. The advantage of that approach is that you may exit algorithm as soon as you get to a pair of corresponding nodes with different values:

def bst_trees_are_identical_impl(p, q):
    if not p and not q:
        return True
    if p and q:
        if p.val != q.val:
            return False
        if not bst_trees_are_identical_impl(p.left, q.left):
            return False
        if not bst_trees_are_identical_impl(p.right, q.right):
            return False
        return True
    return False


def bst_trees_are_identical(p, q):
    return bst_trees_are_identical_impl(p, q)


class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        return bst_trees_are_identical(p, q)

Hope that helps.

Answer 3

Also, is it the most optimal way to solve the problem?

I don;t think so. You are recursively using generators, so if your tree has n nodes, you'll have created and used n generators.

Plus if 2 trees have the same pre-order traversal but a different structure this would be incorrect.

1
 \
  2
 /
3

vs

1
 \
  2
   \
    3

Answer 4

Criticism of Code as Given

As Josh mentioned in his answer, your code as given fails for several cases where two trees have the same preorder traversal but different structure. However, for completeness's sake:

Use Python 3 if at all possible

Python 3 removes a lot of various headaches and annoyances with the language, and in the case of your code, two particular features add a lot of simplicity: yield from and lazy sequence functions (zip, in this case).

In Python 3, your traverse function is as simple as:

def traverse(tree):
    if tree is None:
        yield None
    else:
        yield tree.val
        yield from traverse(tree.left)
        yield from traverse(tree.right)

And your import of izip is unnecessary.

Follow PEP 8

One of the nicest things about the Python community is the official style guide; following it guarantees consistency with existing code, and makes it easy for others to read and use your code without any unnecessary surprises. Tools such as flake8 and pycodestyle exist to help you check for conformance.

Use clearer naming conventions

traverse is slightly misleading – it may imply that your function traverses anything, when in fact it only traverses trees. Name it as such (e.g., traverse_tree); better yet, since it's a specific type of traversal (namely, preorder), name it that (traverse_tree_preorder, perhaps).

'isSameTree' is also somewhat misleading: you are not checking if these are the same tree (which is identity), but if they are equivalent trees. The name trees_are_equal might be more fitting.

Try/Catch Block in isSameTree is unnecessary

A for loop terminates when StopIteration is thrown; you don't need to check for it manually.

Avoid using classes unless you need to track state

The purpose of a class is to combine state with behavior; your equality function doesn't need any state, it only needs behavior. If possible, just drop the Solution class altogether.

Conversely, do use classes when you do need state!

Given the context of your code, it might not be possible to directly alter the tree class, but since both of the functions you define only make sense for trees, it would make more sense to place them inside the class definition.

You get some other benefits out of this, too, such as the ability to override __eq__ for the Tree type so that you can use simple tree1 == tree2 syntax.

Code as given, with suggested modifications

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def traverse_preorder(self):
        yield self.value
        if self.left is not None:
            yield from self.left.traverse_preorder()
        if self.right is not None:
            yield from self.right.traverse_preorder()

    def __eq__(self, other):
        # Keep in mind, this doesn't actually check for tree equality!
        for (l, r) in zip(self.traverse_preorder(), other.traverse_preorder()):
            if l != r:
                return False
        return True

Correct Way to Solve the Problem

The simplest way to describe tree equality is actually recursively: two trees are equal if their values are equal and their two pairs of subtrees are equal (this is equivalent to the definition LeetCode provides, but it makes the correct algorithm more obvious).

If we transcribe this definition directly into Python:

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __eq__(self, other):
        return (other is not None and self.value == other.value and
                self.left == other.left and self.right == other.right)

Breaking this down: first, we check that the second tree is not None; then, we check that our values match; then we recursively call __eq__ for both the left and right subtrees. Since __eq__ has a sensible default definition for None, we don't need to do any other edge case checking for those.

Is this solution optimal?

Without doing benchmarking, this solution is likely to be perfectly satisfactory for most cases. However, one major shortcoming is that since it relies on recursion, it is possible to cause a stack overflow if you pass it a binary tree of too much height (specifically, ~1000 nodes tall for CPython). To avoid this, you'll need to manually simulate recursion using a stack; this gets a lot messier, but doesn't suffer from stack overflow:

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __eq__(self, other):
        from collections import deque

        pairs = deque()
        pairs.append((self, other))

        while len(pairs) > 0:
            s, o = pairs.pop()
            if (s is None) != (o is None) or s.value != o.value:
                return False
            else:
                pairs.append((s.left, o.left))
                pairs.append((s.right, o.right))

        return True