Lowest Common Ancestor in a BST

Given a Binary Search Tree (with all values unique) and two node values. Find the Lowest Common Ancestors of the two nodes in the BST.

Example 1:

Input:
              5
           /    \
         4       6
        /         \
       3           7
                    \
                     8
n1 = 7, n2 = 8
Output: 7

Example 2:

Input:
     2
   /   \
  1     3
n1 = 1, n2 = 3 

Output: 2 

method:

We can recursively traverse the BST from root. The main idea of the solution is, while traversing from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 or same as one of the n1 or n2, is LCA of n1 and n2 (assuming that n1 < n2). So just recursively traverse the BST in, if node’s value is greater than both n1 and n2 then our LCA lies in left side of the node, if it’s is smaller than both n1 and n2, then LCA lies on right side. Otherwise root is LCA (assuming that both n1 and n2 are present in BST)

c++ implementation:

Node* LCA(Node *root, int n1, int n2)
{
        if (root == NULL) return NULL; 
  
    if (root->data > n1 && root->data > n2) 
        return LCA(root->left, n1, n2); 
   
    if (root->data < n1 && root->data < n2) 
        return LCA(root->right, n1, n2); 
  
    return root;
}

Time Complexity: O(n) 

space Complexity: O(n) 

where n is the height of the tree.