JuniorJunior (1–3 yrs)CodingPythonAmazonFacebook

Lowest Common Ancestor of BST

Find the lowest common ancestor of two nodes p and q in a BST (both exist in the tree).

Answers use simple, clear English.

Time: O(h)Space: O(1)

Quick interview answer

Walk from the root: if both values are smaller, go left; both larger, go right; otherwise current node splits them and is the LCA. O(h) time.

Detailed answer

Walk from the root: if both values are smaller, go left; both larger, go right; otherwise current node splits them and is the LCA. O(h) time. Binary tree (non-BST) LCA needs parent pointers or recursive subtree search.

Full explanation

Binary tree (non-BST) LCA needs parent pointers or recursive subtree search.

Real example & use case

Taxonomy browser: find the deepest shared category between two products.

Pros & cons

Pros: uses BST order, O(h). Cons: wrong if tree is not a BST.

Code example

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

Practice code · python (view only · no execution)

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

#bst#lca