Lowest Common Ancestor of a Binary Tree

Problem: Lowest Common of a Binary Tree

Most of tree searching problems can be solved by recursion, so can this one. The general idea is if p and q belongs to different subtree of a certain node, then this node is our answer. So we continuously find a node that split p and q into different subtree. Also we need to consider a situation that one of p and q is ancestor of the other, which is quite a different situation from the previous one.

Code in Python:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def contain(self, a, b):
        if a == None:
            return False
        if a == b:
            return True
        return self.contain(a.left, b) or  self.contain(a.right, b)

    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if self.contain(p, q):
            return p
        if self.contain(q, p):
            return q

        if self.contain(root.left, p) and self.contain(root.left, q):
            return self.lowestCommonAncestor(root.left, p, q)
        if self.contain(root.right, p) and self.contain(root.right, q):
            return self.lowestCommonAncestor(root.right, p, q)

        return root

Details about recursion still matter. One is we should deal with boundary as deep as we can. There's no need to deal with boundary early or ugly codes on judgement will be produced. Besides, we should divide situations as clear as we can.