def problem_4_6(node1, node2):
    """ Design an algorithm and write code to find the first common ancestor of
    two nodes in a binary tree. Avoid storing additional nodes in a data
    structure. NOTE: This is not necessarily a binary search tree.

    Solution: traverse from n1 up to the root; for each ancestor, start traversing
    from n2 up to the root until you you hit n1's parent of the root.

    Alternative solution (not the implementation below): at the very least the
    root will be the common ancestor of the two nodes. So, build two linked lists
    with all the nodes on the path from each node to the root. Then traverse the
    two lists until the last element which is common. This uses extra space!
    """
    n1 = node1
    while n1 != None:
        n2 = node2
        while n2 != None:
            if n2 == n1:
                return n1
            n2 = n2.parent
        n1 = n1.parent
    return None