Lowest Common Ancestor in Binary Search Tree

Problem

Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.

Examples

Example 1:

Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 8

Output: 5

Example 2:

Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 4

Output: 3

Explanation: The LCA of nodes 3 and 4 is 3, since a node can be a descendant of itself.

Constraints

• 2 <= The number of nodes in the tree <= 100.
• -100 <= Node.val <= 100
• p != q
• p and q will both exist in the BST.

You should aim for a solution as good or better than O(h) time and O(h) space, where h is the height of the given tree.

Solution

Use p and q to essentially give us a search window. If the largest of p and q is less than the root, then LCA can only exist on the left subtree. Similarly for the right subtree. If we hit a nullptr then LCA is not found. Otherwise, we found it.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case
        if (!root || !p || !q) {
            return nullptr;
        }
        // If largest of p and q less than root val, then LCA can only be on left
        if (std::max(p->val, q->val) < root -> val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        // If smallest of p and q greater than root val, then LCA can only be on the right
        else if (std::min(p->val, q->val) > root -> val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        else {
            return root;
        }
    }
};