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())
def load_tests(loader, tests, ignore):
tests.addTests(doctest.DocTestSuite())
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.