At first I did a very naive approach where I recorded the individual paths down the tree then took the intersection of the paths. I submitted it and it beat 100% of the ruby solutions.
def lowest_common_ancestor(root, p, q) path_p =  find(root,p,path_p) path_q =  find(root,q,path_q) (path_p & path_q).last end def find(root, elem, path) path << root.val if root.val == elem.val return root else if elem.val < root.val return find(root.left, elem, path) else return find(root.right, elem, path) end end end
Then I read the discussion and realized there was a better approach so I changed to the following which only beats 16% of the ruby solutions.
def lowest_common_ancestor(root, p, q) return root if root.nil? if p.val < root.val && q.val < root.val return lowest_common_ancestor(root.left, p, q) end if p.val > root.val && q.val > root.val return lowest_common_ancestor(root.right, p, q) end return root.val end
Does anyone know why I would get that result?