Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia : “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

For example, the lowest common ancestor (LCA) of nodes2and8is6. Another example is LCA of nodes2and4is2, since a node can be a descendant of itself according to the LCA definition.

First, we need to know what BST is.

According to the definition of BST, we will know BST has the following property:

1. For any node, if its left tree isn't empty, then all the nodes's value of the left tree is smaller than their root.
2. For any node, if its right tree isn't empty, then all the nodes's value of the right tree is larger than their root.
3. For any node, their left tree or right tree is also a BST.
4. There is not such two nodes which have the same value.

In this problem, we will know if

one of the nodes is larger than root's value and the other's is smaller than root's value, we can get the result that current root is their LCA;

otherwise, p and q are in the same subtree of current node, which means that both of p,q is larger or smaller than current node.

then we can go on to find the LCA in the same subtree.

And we go back to the same question: the LCA of p, q in previous's root' subtree.

So, we can use iterative or recursive solution.

Code:

Iterative:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root == NULL)    return NULL;
    while((root->val - p->val)*(root->val - q->val) > 0){
        root = (root->val > p->val) ? root->left : root->right;
    }
    return root;
}

Recursive:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root == NULL)    return NULL;
    if((root->val - p->val)*(root->val - q->val) > 0){
        root = (root->val > p->val) ? lowestCommonAncestor(root->left, p, q) : lowestCommonAncestor(root->right, p, q);
    }
    return root;
}