Q59: Lowest Common Ancestor (LCA) of BST & Binary Tree. - DSA Patterns (Multi-Lang)

In Simple Words:

BST: If both $p$ and $q$ are greater than root, go right. If both smaller, go left. The split point is the LCA.
Binary Tree: If current node matches $p$ or $q$, return it. Search left and right. If both return non-null, current node is the LCA.
Time: $O(N)$ (or $O(H)$ for BST) | Space: $O(H)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def lowestCommonAncestorBST(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    curr = root
    while curr:
        if p.val > curr.val and q.val > curr.val:
            curr = curr.right
        elif p.val < curr.val and q.val < curr.val:
            curr = curr.left
        else:
            return curr

def lowestCommonAncestorBT(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestorBT(root.left, p, q)
    right = lowestCommonAncestorBT(root.right, p, q)
    if left and right: return root
    return left if left else right