Lowest Common Ancestor of a Binary Search Tree

Problem: Lowest Common Ancestor of a Binary Search Tree

If we the targets are in different subtrees of root, then root must be their LCA. If root is one of the target, it's also LCA. Besides, LCA is either in root's left subtree or right subtree, which means we can recursively solve it.

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 lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        def search(node):
            if not node: return None
            if node.val == p.val or node.val == q.val:
                return node
            if node.val > p.val and node.val < q.val:
                return node
            if node.val < p.val and node.val > q.val:
                return node
            if p.val < node.val: return search(node.left)
            if p.val > node.val: return search(node.right)
        return search(root)