Lowest Common Ancestor of BST — BST Property Navigation

Problem 375 · Lowest Common Ancestor of a BST

Difficulty: Medium · Pattern: BST LCA

If both p and q < root, go left. If both > root, go right. Else root is LCA.

Solutions

# Python — iterative
def lowestCommonAncestor(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
    return root

// Java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root!=null) {
        if (p.val<root.val&&q.val<root.val) root=root.left;
        else if (p.val>root.val&&q.val>root.val) root=root.right;
        else return root;
    }
    return root;
}

Complexity

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