Site icon Dipin Krishna

Python: Lowest Common Ancestor of a Binary Search Tree

python

Python 3 code to find the Lowest Common Ancestor of a Binary Search Tree

def lowestCommonAncestor(root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if root is None or p is None or q is None:
        return None
 
    if p.val > q.val:
        temp = p
        p = q
        q = temp
 
    current_node = root
    while current_node:
        if p.val <= current_node.val and current_node.val <= q.val:
            return current_node
        else:
            current_node = current_node.left if p.val < current_node.val else current_node.right
 
    return None

Hope it helps.

Exit mobile version