LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

Explanation

To find the lowest common ancestor (LCA) of two given nodes in a binary search tree (BST), we can utilize the properties of a BST. The key idea is to traverse the tree starting from the root and search for a node p and a node q such that their values lie within the range of the current node's value. This way, we can determine the LCA by following the path where the values of p and q diverge.

1. Start from the root node.
2. If both p and q are greater than the current node's value, move to the right subtree.
3. If both p and q are smaller than the current node's value, move to the left subtree.
4. If the current node's value lies between p and q, then the current node is the LCA.
5. Return the LCA node.

The time complexity for this approach is O(h), where h is the height of the tree. In the worst case, the height of a BST can be O(n), where n is the number of nodes in the tree, making the time complexity O(n). The space complexity is O(1) as we are using constant extra space for the algorithm.

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;
}