Lowest Common Ancestor of a BST

Share

Given a BST, find the lowest common ancestor (LCA) of two given nodes p and q. LCA is defined as the lowest node that has both p and q as descendants.

Example 1
Input: root=[6,2,8,0,4,7,9], p=2, q=8 → Output: 6
Example 2
Input: root=[6,2,8,0,4,7,9], p=2, q=4 → Output: 2

Solution Approach

Exploit BST property: if both p and q are less than root, LCA is in left subtree. If both greater, in right subtree. Otherwise, root is the LCA.

  • While root != null:
  • If both p.val < root.val and q.val < root.val: go left.
  • Else if both > root.val: go right.
  • Else: return root (it is the split point).
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;
    }
}
  • Time Complexity: O(H)
  • Space Complexity: O(1)