Check if two binary trees are equal

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

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.

StackExchange Code Review Q#159137, answer score: 7