Lowest Common Ancestor of a Binary Search Tree medium

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

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,null,null,null,null,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.

Steps

1. Handle Base Cases: If the root is null, or either p or q is equal to the root, return the root.
2. Recursive Search: If both p and q are less than the root's value, recursively search the left subtree. If both are greater than the root's value, recursively search the right subtree.
3. LCA Found: If p and q are on opposite sides of the root (one is less, one is greater), then the root itself is the LCA.

Explanation

A Binary Search Tree (BST) has the property that all nodes in the left subtree are smaller than the root, and all nodes in the right subtree are larger than the root. This property is crucial for efficiently finding the LCA. The algorithm leverages this property: if both nodes are smaller, the LCA must be in the left subtree; if both are larger, the LCA must be in the right subtree; otherwise, the current node is the LCA because the nodes are on opposite sides.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) return root;

        if (p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else {
            return root;
        }
    }
};

Complexity

• Time Complexity: O(H), where H is the height of the BST. In the worst case (a skewed BST), H could be equal to N (number of nodes). In a balanced BST, H is log(N).
• Space Complexity: O(H) in the worst case due to the recursive call stack. In a balanced BST, this would be O(log N). In a skewed BST, this would be O(N).