Skip to content
AI360Xpert
Back to Trees
Medium

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes `p` and `q` as the lowest node in `T` that has both `p` and `q` as descendants (where we allow a node to be a descendant of itself)."

Examples

Input:root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output:6
The LCA of nodes 2 and 8 is 6.
Input:root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output:2
The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Input:root = [2,1], p = 2, q = 1
Output:2
The LCA is the root node 2.

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

Approach

Intuition: In a BST, the left subtree contains values smaller than the root, and the right subtree contains values greater. If both `p` and `q` are greater than the root, the LCA must be in the right subtree. If both are smaller, the LCA must be in the left subtree. If one is greater and one is smaller (or one equals the root), then the current node is the LCA. Logic: 1. Initialize a pointer `current` to the root of the tree. 2. Enter a while loop that runs as long as `current` is not null. 3. Check if both `p.val` and `q.val` are greater than `current.val`. If they are, it means both nodes are in the right subtree. Update `current` to `current.right`. 4. Check if both `p.val` and `q.val` are less than `current.val`. If they are, it means both nodes are in the left subtree. Update `current` to `current.left`. 5. If neither of the above conditions is met, it means `p` and `q` are on different sides of `current` (or one of them is equal to `current.val`). This implies `current` is the lowest common ancestor. Return `current`.

Complexity Analysis

Time Complexity
O(h)
Space Complexity
O(1)

This iterative approach achieves O(1) space complexity by avoiding recursion overhead.

Solution.java
class Solution {    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        TreeNode current = root;                while (current != null) {            if (p.val > current.val && q.val > current.val) {                // Both in right subtree                current = current.right;            } else if (p.val < current.val && q.val < current.val) {                // Both in left subtree                current = current.left;            } else {                // Split occurs, this is the LCA                return current;            }        }                return null;    }}