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.

• alecxe: Great point about simplifying the traversal! The Solution was a leetcode constraint, yeah. Thank you.

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.

• gntskn: I believe that the OP's code already short-circuits and returns as soon as a single pair of nodes are unequal; ironically, your code solves the actual problem in OP's code, which is that it only checks for equivalent traversals (your code checks for true equivalency) :p
• coderodde: @gntskn There are many words that I don't understand. :p

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

• coderodde: It would seem that in this case we have a relaxation: the input trees are not expected to be valid binary search trees. All we do, is make sure that both the trees are of the same topology and content.

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