Lowest common ancestor

// Lowest common ancestor in an unordered binary tree given two values
// Not a binary search tree. Unordered binary tree.
// Find the lowest common ancestor of the two nodes represented by val1 and val2
// No Guarantee that val1 and val2 exist in tree. If one value doesn't exist in the tree return NULL.
// There are NO duplicate values
// You can use extra memory, helper functions. You can modify the node struct but you can't add a parent pointer.
// You have to beat O(N*N) for a solution. Where N is the number of the nodes in the tree.

Answer
A = List of the ancestors of A (see function below)
B = List of the ancestors of B
compare A and B

Complexity = O(N+N+N) = O(N) [see note below to reduce complexity]

def ancestor(tree,val):
  if tree.left and tree.left.val == val:
         return [tree]
  elif tree.right and tree.right.val == val:
         return [tree]
  else:
     if tree.left:
       l_ancestors = ancestor(tree.left,val)
       if len(l_ancestors) > 0:
          return [tree] + l_ancestors
     if tree.right:
       r_ancestors = ancestor(tree.right,val)
       if len(r_ancestors) > 0:
          return [tree] + r_ancestors
     return []  

Note: if we had been using a balanced, the maximum number of ancestors would have been log(N)-1 instead of N. Thus, the overall complexity would have been O(log(N))