Skip to main content

Lowest Common Ancestor of a Binary Search Tree

Question​

What is the lowest common ancestor of two nodes in a binary search tree?

Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5]
q = [2,4]

Output: 2

Solution​

all//Lowest Common Ancestor of a Binary Search Tree.py


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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # If both p and q are larger than root, then LCA must be in right subtree
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right,p,q)
        # If both p and q are smaller than root, then LCA must be in left subtree
        elif root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        # Otherwise root is the LCA
        else:
            return root