Lowest Common Ancestor Of A Binary Search Tree - Leetcode Solution

The problem is to find the lowest common ancestor (LCA) of two nodes in a binary search tree (BST).

A BST is a tree where the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key.

The solution to this problem involves traversing the BST from the root node until we find a node that lies between the two nodes whose LCA we are trying to find. This node will be the LCA.

Algorithm:

1. Start at the root node of the BST.
2. If the values of both nodes are less than the current node's value, move to the left subtree.
3. If the values of both nodes are greater than the current node's value, move to the right subtree.
4. If one of the nodes has the same value as the current node, that node is the LCA.
5. If both nodes have values that are less than or greater than the current node's value, the current node is the LCA.
6. If the values of the two nodes lie on either side of the current node's value, move down the tree recursively until the LCA is found.

Code:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else if(p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else {
            return root;
        }
    }
};

In this code, we first check if both nodes are greater than or less than the current node's value. If they are, we move to the right or left subtree, respectively. If both nodes have values that are less than or greater than the current node's value, the current node is the LCA. If the values of the two nodes lie on either side of the current node's value, we move down the tree recursively until the LCA is found.

1