Midokura homework

treenode.py

#!/usr/bin/env python

# Implement the 'findFirstCommonAncestor' method that given another TreeNode
# finds the first (deepest in the tree) common ancestor of 'this' TreeNode and
# the one passed to the method. Assume that each TreeNode is a node in a
# binary tree. You may add methods but not data members to the TreeNode class.
#
# Solution
#
# To approach this exercise I create two lists with the paths of the two
# TreeNodes from # themselves to the top of the tree. Then I compare the two
# lists and the last element that's in both lists is the first common ancestor
#
# Notes:
# 1. i've avoided trivial checks in order to improve readability and focus more
#    in algorithm discusion in code review
# 2. It is not easy to calculate memory consumption in python objects
#    (http://stackoverflow.com/questions/33978/find-out-how-much-memory-is-being-used-by-an-object-in-python)
#    but assuming a TreeNode needs N bytes and the full Tree is M depth,
#    we will need in memory at maximum 2*M*N bytes (since we build two paths
#    from the TreeNode to top of the Tree)
# 3. In time terms... i guess this is an O(log N) algorithm
# 4. I've spent one hour more or less in this solution


class TreeNode(object):

    def __init__(self, parent=None):
        self.parent = parent

    def find_first_common_ancestor(self, other):
        """ Given two TreeNodes, return the deepest common ancestor."""
        # Trivial cases. the inputs are the same or one is parent
        # of the other one
        if self == other:
            return self.parent
        elif self.parent == other:
            return other
        elif self == other.parent:
            return self
        else:
            # Build two lists with all the ancestors
            self_list = self.build_list_of_ancestors()
            other_list = other.build_list_of_acestors()
            zipped = zip(self_list, other_list)
            # 'zipped' is a list of tuples were the n-th element of the list is
            # tuple of TreeNodes at the n-th level depth. For instance:
            #
            # [('a', 'a'), ('b', 'b'), ('c', 'd'), ('e', 'f')].
            #
            # The first element is the root of the TreeNode and it always
            # should be the same. In this case, the most common ancestor
            # is 'b'
            return [i for i, j in zipped if i == j][-1]

    def _build_list_of_ancestors(self, ancestors=[]):
        """ Recursive function to build all the ancestors.

        Create a list with all the ancestors of a TreeNode.
        The first element will be the root of the binary tree.
        """
        ancestors.extend(self)
        if self.parent is None:
            return list(reversed(ancestors))
        else:
            return self.parent._build_list_of_ancestors(ancestors)