# 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).”

###### 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.