Lowest Common Ancestor in a BST

Given a Binary Search Tree (with all values unique) and two nodes n1 and n2 (n1 != n2). You may assume that both nodes exist in the tree. Find the Lowest Common Ancestor (LCA) of the given two nodes in the BST.

LCA between two nodes n1 and n2 is defined as the lowest node that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

Examples:

Input: root = [5, 4, 6, 3, N, N, 7, N, N, N, 8], n1 = 7, n2 = 8
        
Output: 7
Explanation: 7 is the closest node to both 7 and 8, which is also an ancestor of both the nodes.

Input: root = [20, 8, 22, 4, 12, N, N, N, N, 10, 14], n1 = 8, n2 = 14
                
Output: 8
Explanation: 8 is the closest node to both 8 and 14, which is also an ancestor of both the nodes.

Input: root = [2, 1, 3], n1 = 1, n2 = 3
        
Output: 2
Explanation: 2 is the closest node to both 1 and 3, which is also an ancestor of both the nodes.

Constraints:
1 <= number of nodes <= 10⁵
1 <= node->data <= 10⁵
1 <= n1, n2 <= 10⁵

Approach 01:

class Solution {
  public:
    Node* LCA(Node* root, Node* node1, Node* node2) {
        // Traverse the BST to find the Lowest Common Ancestor
        while (root != nullptr) {
            if (node1->data < root->data && node2->data < root->data) {
                root = root->left;  // Move left if both nodes are smaller
            }
            else if (node1->data > root->data && node2->data > root->data) {
                root = root->right;  // Move right if both nodes are greater
            } else {
                return root;  // Found the LCA
            }
        }
        return nullptr;
    }
};

class Solution:
    def LCA(self, root: 'Node', node1: 'Node', node2: 'Node') -> 'Node':
        # Traverse the BST to find the Lowest Common Ancestor
        while root is not None:
            if node1.data < root.data and node2.data < root.data:
                root = root.left  # Move left if both nodes are smaller
            elif node1.data > root.data and node2.data > root.data:
                root = root.right  # Move right if both nodes are greater
            else:
                return root  # Found the LCA
        
        return None

Time Complexity:

• Best and Average Case:

  Since the function follows the structure of a Binary Search Tree (BST), it moves either left or right at each step, reducing the problem size approximately by half. This results in a time complexity of \( O(\log n) \) for a balanced BST.

• Worst Case:

  If the BST is skewed (like a linked list), the function may need to traverse all nodes, leading to \( O(n) \) complexity.

Space Complexity:

• Iterative Approach:

  The function uses an iterative method, so it does not incur additional recursive stack space. The space complexity is \( O(1) \).