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

Question

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.

Answer 1

OK - One quick observation. I think when you are asked to check for Symmetry of a Binary tree - it is not structural symmetry alone, you would have to take the "values" into account as well. For that reason, I think the "value" attribute is missing from your node definition.

class TreeNode:
     def __init__(self, x):
         self.val = x <------ you might want to add this.
         self.left = None
         self.right = None