2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Yes, values, I considered adding them, but they're not what the problem really seemed to be about (which to me was structure and recursion), but yes, it's a simple matter to add values and add them as a check in the equality method. \$\endgroup\$ – Aaron Hall May 29 '16 at 4:05
  • \$\begingroup\$ @AaronHall I think if you opted to not include them then that should be clearly part of the docstring, to prevent confusion for users. \$\endgroup\$ – SuperBiasedMan May 30 '16 at 10:52
  • \$\begingroup\$ "Bare Bones", I thought, communicated that. \$\endgroup\$ – Aaron Hall May 30 '16 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.