Given a binary search tree (BST), find the lowest common ancestor (LCA) of two specified nodes. The LCA is defined as the deepest node that is an ancestor to both nodes, where a node can be its own anecstor.

For example, consider a BST with root = [6,2,8,0,4,7,9,null,null,3,5].

Example 1:

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.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, as a node can be its own ancestor.

Constraints:

• All node values are unique.
• p and q are different nodes and exist in the BST.

Approach: Leveraging BST Properties

Since the tree is a BST, we can exploit its ordering property to find the LCA efficiently without traversing all nodes. For any node current:

• If current.val is greater than both p.val and q.val, then both nodes lie in the left subtree. Move current to current.left.
• If current.val is less than both p.val and q.val, then both nodes lie in the right subtree. Move current to current.right.
• Otherwise, current is the LCA, as p and q are on different sides or one is current itself.

This method has a time complextiy of O(N) in the worst case (where N is the number of nodes) and a space complexity of O(1).

Implemantation

C++:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* current, TreeNode* p, TreeNode* q) {
        while (true) {
            if (current->val > p->val && current->val > q->val) {
                current = current->left;
            } else if (current->val < p->val && current->val < q->val) {
                current = current->right;
            } else {
                return current;
            }
        }
    }
};

Python:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, current: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        while True:
            if current.val > p.val and current.val > q.val:
                current = current.left
            elif current.val < p.val and current.val < q.val:
                current = current.right
            else:
                return current