0235.md

235. Lowest Common Ancestor of a Binary Search Tree

Level:

Topic:

Similar Problem:

• 236. Lowest Common Ancestor of a Binary Tree
• 1644. Lowest Common Ancestor of a Binary Tree II
• 1650. Lowest Common Ancestor of a Binary Tree III

Question

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Intuition

Recursive:

Since it's a BST,

• if the current node val is greater than both p and q, traverse the left subtree
• if the current ndoe val is less than both p and q, traverse the right subtree
• if neither, then it's the ancestor

Code

Time: O(n)
Space: O(n)

Recursive

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return null;

    if (root.val > p.val && root.val > q.val)
        return lca(root.left, p, q);
    else if (root.val < p.val && root.val < q.val)
        return lca(root.right, p, q);
    else
        return root;
}