235. Lowest Common Ancestor of a Binary Search Tree

Let's discuss problem no 235 at leetcode i.e 235. Lowest Common Ancestor of a Binary Search Tree. Problem Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Here we are supposed to find the lowest common ancestor in a binary search tree. The lowest common ancestor is the node which is the first common ancestor of any given node.

If we look closely there are the following cases.

1. One of the given nodes itself is the common ancestor.
2. Since it's a BST, all the elements lower to the current node will be on the left side and all the elements higher will be on the right side. which means >
   • If the current node value is lesser than both elements, our common ancestor will be on the right side
   • If the current node value is greater than both elements, our common ancestor will be on the left side
   • If one of the values is higher and another is lower than the current element, it is the ancestor of both elements, actually this is the lowest common ancestor.

Let's check the code for it.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root.val>p.val && root.val>q.val) 
            return lowestCommonAncestor( root.left , p, q);
        if(root.val<p.val && root.val<q.val) 
            return lowestCommonAncestor( root.right , p, q);

       return root;


    }
}