# LeetCode: 235. Lowest Common Ancestor of a Binary Search Tree

**The Problem**

Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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**

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

**Constraints:**

- The number of nodes in the tree is in the range
`[2, 10`

.^{5}] `-10`

^{9}<= Node.val <= 10^{9}- All
`Node.val`

are.**unique** `p != q`

`p`

and`q`

will exist in the BST.

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) return NULL;
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;
}
```

🧠

Github with all the solution including test cases. Also an alternative approach.

This code helps find the common ancestor of two nodes in a tree, where the nodes are organized from the minimum to the maximum value.

- If the tree is empty (
`root == NULL`

), it stops searching and returns nothing. - It checks if both nodes (p and q) have values less than the current node (root). If they do, it continues the search on the left side of the tree, where nodes with smaller values are located.
- If both nodes have values greater than the current node (root), it continues the search on the right side of the tree, where nodes with larger values are located.
- If one node has a smaller value and the other has a larger value than the current node, it means the current node is the common ancestor, so it returns that node.