Lowest Common Ancestor of a Binary Search Tree – LeetCode Solution [Easy]

Problem

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 Tree that has both p and q as descendants (where we allow a node to be a descendant of itself).”

LeetCode Problem Link

Input

root of binary search tree, node p and node q

Output

Lowest common ancestor of nodes p and q.

Constraints

• 2 <= Number of Nodes in the Tree ≤ 100000
• -10^9 <= Value of Nodes ≤ 10^9
• All nodes are unique

Sample Input

root = [6, 2, 8, 0, null, null, 10, null, 1, 9, 22]
p = 8, q = 22

Sample Output

8

Code Implementation

class Solution {
public:
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) {
            return NULL;
        }
        
        if (root == p || root == q) {
            return root;
        }
        
        TreeNode *lNode = lowestCommonAncestor(root->left, p, q);
        TreeNode *rNode = lowestCommonAncestor(root->right, p, q);
        
        if (lNode && rNode) {
            return root;
        }
        
        return lNode != NULL ? lNode : rNode;
        
    }
};

Time complexity: O(n), where n is the number of nodes in tree. This is because it’s a simple tree traversal.