node_parent.py

class Node:
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent

def ancestors(node):
    # return all parent nodes including this node
    ancestor_nodes = []
    ancestor_nodes.append(node)
    parent = node.parent
    while parent:
        ancestor_nodes.append(parent)
        parent = parent.parent
    return ancestor_nodes

def lca(node1, node2):
    # return the least common ancestor for nodes in a N-ary tree
    if node1.parent == node2.parent:
        return node1.parent

    for child_node1 in ancestors(node1):
        for child_node2 in ancestors(node2):
            if child_node1 == child_node2:
                return child_node1


# build the tree from values from PDF
one = Node(1, None)
three = Node(3, one)
seven = Node(7, three)
six = Node(6, three)
two = Node(2, one)
four = Node(4, two)
five = Node(5, two)
eight = Node(8, four)
nine = Node(9, four)


print lca(eight, five).value