Find the Lowest Common Ancestor of two given nodes of a Binary Search Tree

Given two nodes and the root node of a binary search tree,

Find the lowest common ancestor of those two nodes.

A common ancestor node is a node who is the parent of both the given nodes.

Lowest common ancestor means there is no other common ancestor node which is lower than this node in the tree which is parent to both the nodes.

For example,

In the above binary search tree,

Given the nodes 2 and 8,

their lowest common ancestor is 6.

Given the nodes 3 and 5 ,

their lowest common ancestor is 4 and so on.

Try out the solution here:

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Assumptions:

• Both the nodes for which you need to find the LCA are present in the tree
• Both the node values are unique .

Solution:

Hint:

Branch left of the tree if both the node values are less than the root.

Branch right of the tree if both the node values are greater than the root.

When the above conditions no longer match , then one node is present in the left subtree and the other in the right subtree , so return that node.

Here is the recursive version of the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     
        
        
        int rootVal = root.val;
        int pVal = p.val;
        int qVal = q.val;
        
        
        if(p.val < rootVal && q.val < rootVal){
            
            return lowestCommonAncestor(root.left,p,q);
        }else if(p.val > rootVal && q.val > rootVal){
            
           return lowestCommonAncestor(root.right, p , q);
        }else{
            
            return root;
        }
   
        
    }
}

Time complexity:

In the worst case(skewed tree) we will iterate through all the nodes so time complexity is O(n)

Space complexity:

Since we use recursion , we need O(n) space for the recursive stack.

Here is the iterative version of the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

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

        
        while(root != null){
  
                 if(p.val < root.val && q.val < root.val){
            
            
                        root = root.left;
                 }else if(p.val > root.val && q.val > root.val){
            
                        root = root.right;
                  }else{
        
            
                        return root;
                    }
         }
        
        return null;
        
        
    }
}

Time complexity:

Similar to the previous one , for the worst case it is O(n)

Space complexity:

We are not using any additional memory so space complexity is O(1)

In both the cases , we keep branching left or right based on both the node values and stop when they both don’t obey the two conditions.

At this stage one of the nodes is in the left tree and the other in the right , so we return the root node.

That’s it!