Java Solution (Addresses a special, untested case)


  • 0
    A

    I see a lot of Java solutions that seem to assume if the two target nodes' values are greater than the root's value, the LCA must be in the right subtree (and the analogous situation on the left subtree). Although all test cases seem to pass with this approach, there are cases where this is assumption is not true. By definition, it is possible for a BST to have all identical values. Now, inspecting node values doesn't really allow us to deduce where the references to the nodes are in the tree. To account for this, we would have to check all O(N) nodes in the BST (therefore also allowing this solution to work on any tree, not just a BST). Here is my accompanying solution:

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == null || q == null) {
                return null;
            }
            
            if (root == p || root == q) {
                return root;
            }
            
            TreeNode leftCall = lowestCommonAncestor(root.left, p, q);
            TreeNode rightCall = lowestCommonAncestor(root.right, p, q);
            
            if (leftCall == null) {
                return rightCall;
            }
            
            if (rightCall == null) {
                return leftCall;
            }
            
            return root;
        }
    }
    

    In essence, we cannot assume that just because we are given a BST, it holds a certain property that helps us achieve a faster solution. (Unless we had received clarification from an interviewer or such.) Just a friendly thought. :)


Log in to reply
 

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