Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Scala

trait TreeNode {
  def value: Int
  def left: TreeNode
  def right: TreeNode
}

object EmptyNode extends TreeNode {
  def value = throw new Error("accessing empty node")
  def left = throw new Error("accessing empty node")
  def right = throw new Error("accessing empty node")
}

class NoneEmptyNode(var value: Int, var left: TreeNode = EmptyNode, var right: TreeNode = EmptyNode) extends TreeNode

def lowestCommonAncestor(root:TreeNode, p:TreeNode, q:TreeNode):TreeNode = {
  if (root == EmptyNode || root == p || root == q) return root
  val left:TreeNode = lowestCommonAncestor(root.left, p, q)
  val right:TreeNode = lowestCommonAncestor(root.right, p, q)
  if (left != EmptyNode && right != EmptyNode) root
  else if (left != EmptyNode) right
  else left
}

Python

def lowestCommonAncestor(root, p, q):
    if p is root or q is root or not root:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right