Return to Revisions

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.