node_three_second.py

"""
I use logic that use just node values, which is a bit simpler
"""

class Node(object):

	def __init__(self, value, parentNode):
		self.value = value
		self.parent = parentNode

def node_ancesors(node):
	ancesors = [node.value, ]

	while node.parent:
		ancesors.append(node.value)
		node = node.parent

	return ancesors


def lca(node1, node2):
	ancs1 = node_ancesors(node1)
	ancs2 = node_ancesors(node2)

	closest = max(set(ancs1) & set(ancs2))

	print closest


def improved_lca(node1, node2):

	if node1.value == node2.value:
		return node1.value

	if not node1.parent:
		return node1.value

	if not node2.parent:
		return node1.value

	if node1.parent.value == node2.parent.value:
		return node1.parent.value

	return lca(node1, node2)