Java: Lowest Common Ancestor of a Binary Search Tree

Thought Process

The problem requires finding the lowest common ancestor (LCA) of two nodes in a Binary Search Tree (BST). The key property of a BST is that for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. We use this property to determine the LCA. If both nodes are greater than the current root, we search in the right subtree. If both nodes are smaller, we search in the left subtree. Otherwise, the current root is the LCA. 

/**
 * 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) {
        
        if(root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right,p,q);
        else if(root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left,p,q);
        else
            return root;
    }
}

Code Complexity

Time Complexity: O(h)

The algorithm traverses the height of the tree, making it O(h), where 'h' is the height of the BST. In the worst case, this is O(n) for a skewed tree.

Space Complexity: O(h)

The algorithm uses recursion, which consumes stack space proportional to the height of the tree. In the worst case, this is O(n) for a skewed tree.

Code copied!