# Check binary tree symmetry by reversing, checking equality, coverage tested, makefile

A few weeks ago I recall a HackerNews story (found it again: "I Don't Want to Hire You If You Can't Reverse a Binary Tree") about reversing a binary tree (with, as I remember it, the end goal being to test for symmetry by testing the reverse for equality with the original).

I started hacking this implementation up as I was on the subway headed to work, with the intention of posting it here, but lost track of it until today. (A friend at my Python meetup was working on a similar problem today and jogged my memory.)

Here's my implementation, tested for coverage, with Makefile and output. Note that I leave out a "value" attribute/argument because including it is trivial and the point of the exercise is to have a bare-bones implementation that solves the harder problems of recursion and inversion, while following best practices from an academic standpoint. The values just get in the way.:

class Node(object):
"""Bare-bones Binary Node with a left and right attribute for
pointing at more Node objects to create a binary tree.
Used to demonstrate testing for tree symmetry by reversing
the tree and testing for equality.

>>> tree = Node(Node(), Node())
>>> tree
Node(Node(None, None), Node(None, None))
>>> tree.is_symmetric()
True
>>> tree_2 = Node(Node())
>>> tree_2
Node(Node(None, None), None)
>>> tree_2.is_symmetric()
False
"""

__slots__ = 'left', 'right'

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

def __reversed__(self):
return type(self)(None if self.right is None else reversed(self.right),
None if self.left is None else reversed(self.left))

def __eq__(self, other):
if other is None:
return False
else:
return (self.left, self.right) == (other.left, other.right)

def __ne__(self, other):
return not self == other

def __repr__(self):
return '{0}({1}, {2})'.format(type(self).__name__,
repr(self.left), repr(self.right))

def is_symmetric(self):
return self == reversed(self)


Here are the tests (imported are doctest and unittest modules):

class Tester(unittest.TestCase):

@classmethod
def setUpClass(cls):
cls.tree = Node(Node(Node(),
Node()),
Node(Node(),
Node()))

def test_equals_zero_deep(self):
self.assertEqual(Node(), Node())

def test_not_equals_zero_deep(self):
self.assertNotEqual(Node(), None)

def test_symmetry(self):
self.assertTrue(Node().is_symmetric())
self.assertTrue(Node(Node(),
Node()).is_symmetric())
self.assertTrue(self.tree.is_symmetric())

def test_asymmetry(self):
self.assertFalse(Node(Node(Node()),
Node(Node(),
Node())).is_symmetric())

def test_tricky_asymmmetry(self):
self.assertFalse(Node(Node(Node(Node()),
Node()),
Node(Node(Node()),
Node())).is_symmetric())

def test_tricky_symmmetry(self):
self.assertTrue(Node(Node(Node(Node()),
Node()),
Node(Node(),
Node(None, Node()))).is_symmetric())

return tests

if __name__ == '__main__':
unittest.main(exit=False)


Here's my Makefile:

.PHONY: all
all: pycoverage pylint

.PHONY: pycoverage
pycoverage: pycov2 pycov3

.PHONY: pycov2
pycov2:
python -m coverage run -m unittest discover
python -m coverage report

.PHONY: pycov3
pycov3:
python3 -m coverage run -m unittest discover
python3 -m coverage report

.PHONY: pylint
pylint:
python -m flake8 .

.PHONY: publish
publish:
python -m coverage html
firefox htmlcov/index.html


And here's my test output:

~/reverse_tree$make python -m coverage run -m unittest discover ....... ---------------------------------------------------------------------- Ran 7 tests in 0.002s OK python -m coverage report Name Stmts Miss Cover --------------------------------------- test_reverse_tree 41 1 98% python3 -m coverage run -m unittest discover ....... ---------------------------------------------------------------------- Ran 7 tests in 0.003s OK python3 -m coverage report Name Stmts Miss Cover --------------------------------------- test_reverse_tree 41 1 98% python -m flake8 . ~/reverse_tree$


The remaining 2% is the call to unittest.main(). I did place the tests and the primary object in the same file for simplicity. Please review.

class TreeNode: