11ms, 3 line Java Solution and a general solution for all trees.


  • 0
    J

    Solution for a BST
    '''
    public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

       if(root==null || root==p || root==q) return root;
       
      //Root will be the LCA if p and q are on either side of root.
       if((p.val<=root.val && q.val > root.val) || (p.val>root.val && q.val <= root.val)) return root;
        
       return p.val<=root.val ? lowestCommonAncestor(root.left,p,q) : lowestCommonAncestor(root.right,p,q);
        
    }
    

    }
    '''

    A general solution for all trees.

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

        if(root==null || root==p || root==q) return root;
        
        boolean leftP =isPresent(root.left,p);
        boolean leftQ = isPresent(root.left,q);
        
        if(leftP != leftQ) return root;
        
        return leftP==true ? lowestCommonAncestor(root.left,p,q) : lowestCommonAncestor(root.right,p,q);
        
    }
    
    public boolean isPresent(TreeNode root,TreeNode p){
        
        if(root==null || p==null) return false;
        if(root==p) return true;
            
        return isPresent(root.left,p) || isPresent(root.right,p);
    }
    

    }
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.