Lowest Common Ancestor of a Binary Search Tree

Problem

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Constraints:

• The number of nodes in the tree is in the range [2, 10<sup>5</sup>].

• -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>

• All Node.val are unique.

• p != q

• p and q will exist in the BST.

Solution

Please check the general idea of Lowest Common Ancestor.

Idea: The main idea is to use the properties of a Binary Search Tree. If p and q are on the left and right sides of the parent, then the current node is the LCA. Otherwise, if both are smaller than the current node, we move to the left. If they are larger, we move to the right.

Time - O(n)

Space - O(H)

class Solution {

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

        if(root == null){
            return null;
        }

        int curr = root.val;

        // (p,q) < curr (both on left)
        if (curr>p.val && curr>q.val){
            return lowestCommonAncestor(root.left, p,q);
        }

        // curr < (p,q) (both on right)
        if (curr<p.val && curr<q.val){
            return lowestCommonAncestor(root.right,p,q);
        }

        return root;
    }
}