Lowest Common Ancestor of a BST

Problem

Given a BST and two of its nodes, return their lowest common ancestor (LCA).

Constraints

• 2 ≤ nodes ≤ 10⁵
• p and q are present, distinct

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def lowestCommonAncestor(self, 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

Java

class Solution {
    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 null;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.