Return to Answer

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:

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:

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

For loop in isSameTree is also unnecessary: use all , map , and operator.__eq__

def trees_are_equal(left, right):
 import operator
 return all(map(operator.__eq__, 
 zip(traverse(left), traverse(right))

Avoid using classes unless you need to track state

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!
 import operator
  return all(map(operator.__eq__, zip(self.traverse_preorder(), 
 other.traverse_preorder())))

Avoid using classes unless you need to track state

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