Lowest Common Ancestor of a Binary Search Tree

Problem Statement

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).”

_______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Approach

• Since this is a Binary Search Tree, we know that the left node will be smaller than or equal to the root node and the right node will be greater than the root node.This basically involves checking the below edge cases:
• If root is null, then return null
• If either of the nodes is the root node then root node is the LCA (Lowest Common Ancestor)
• If one of the nodes is greater than the root and another is less than the root then root is the LCA
• If both the nodes given are same, then there is no LCA, return null
• If both nodes are smaller than the root, then recursively call the LCA function to compute steps 1 to 4 on the left node of the root.
• If both nodes are greater than the root, then recursively call the LCA function to compute steps 1 to 4 on the right node of the root.

Run Time

Assuming that the tree is balanced, worst case run time is O(log n). This is because each time we are either processing the left side of the binary search tree or the right side of the binary search tree.

Java Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(p.val == q.val){
            return null;
        }
        if ((p.val == root.val) || (q.val == root.val)){
            return root;
        }if(((p.val < root.val) && (q.val > root.val)) || ((q.val < root.val) && (p.val > root.val))){
            return root;
        }if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }else{
            return lowestCommonAncestor(root.right,p,q);
        }
        
    }
}