Lowest common ancestor, problem z rekursją.

Cześć, rozwiązuję sobie zadanie od Dayli Coding Problem, treść: "Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. Assume that each node in the tree also has a pointer to its parent."
Moje rozwiązanie:

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

def findLCA(first, second):
    if first.parent == None and second.parent == None:
        return None
    else:
        if first.parent.value == second.parent.value:
            # return first.parent.value # return None
        
            print('Value: {}'.format(first.parent.value)) # Wypisze poprawną wartość
        else:
            if first.parent != None:
                first = first.parent
            if second.parent != None:
                second = second.parent
            findLCA(first, second)

def getValueNode(root, value):
    if root == None:
        return None
    if root.value == value:
        return root

    res1 = getValueNode(root.right, value)
    res2 = getValueNode(root.left, value)
    return res1 or res2

root = Node(1, None)
root.left = Node(2, root)
root.left.left = Node(4, root.left)
root.left.right = Node(5, root.left)

root.right = Node(3, root)
root.right.right = Node(7, root.right)
root.right.left = Node(6, root.right)

print(findLCA(getValueNode(root, 4), getValueNode(root, 6)))

I teoretycznie ten kod działa - dla tego przypadku program powinien zwrócić 1.
Ale tak się nie dzieje zwrócona zostaje wartość None, ale jeśli wypiszę sobie liczbę print('Value: {}'.format(first.parent.value)) to rostanie podana prawidłowa. Wygląda to tak jak by program ignorował polecnie return (wiem że ten warunek jest spełniony i program tam wychodzi). Właściwe pytanie, dlaczego first.parent.value zwraca None jeśli po zakomentowaniu wypisuję tę wartość i jest prawidłowa(wtedy też zwraca None ale to jest wtedy zrozumiałe bo funkcja nic nie zwraca).

Wygląda na to, że zwyczajnie docierasz do końca funkcji bez zwracania niczego - innymi słowy nie rozpatrzyłeś wszystkich przypadków (algorytm jest błędny).

Dobra znalazłem rozwiązanie:

def findLCA(first, second):
    if first.parent == None and second.parent == None:
        return None
    else:        
        if first.parent != None:
            first = first.parent
        if second.parent != None:
            second = second.parent
        if first.parent.value == second.parent.value:
            return first.parent.value # return None
        findLCA(first, second)

Będziesz musiał mocniej przyczaszkować.

  .--6
  |  |
  |  `--5
--4   
  |  .--3
  |  |    
  `--2
     |
     `--1

W powyższym drzewie: LCA(1, 2) = 2, LCA(2, 5) = 4, LCA(4, 4) = 4.