# Leetcode Lowest Common Ancestor of a Binary Search Tree problem solution

In this Leetcode Lowest Common Ancestor of a Binary Search Tree problem solution we have 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).”

## Problem solution in Python.

```class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root:
return
elif (root.val >= p.val and root.val <= q.val) or (root.val <= p.val and root.val >= q.val):
return root
elif root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left,p,q)
else:
return self.lowestCommonAncestor(root.right,p,q)
```

## Problem solution in Java.

```class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null)
return root;
if(root.val==p.val || root.val==q.val)
return root;
if(root.val>p.val && root.val>q.val)
return lowestCommonAncestor(root.left,p,q);
if(root.val<p.val && root.val<q.val)
return lowestCommonAncestor(root.right,p,q);
return root;
}
}
```

## Problem solution in C++.

```class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* ll = p;
TreeNode* hh = q;
if(p->val > q->val)
{
ll=q;
hh=p;
}
while((ll->val!=root->val && hh->val!=root->val) && (ll->val > root->val || root->val > hh->val))
{
if(ll->val > root->val)
{
root=root->right;
}
else if(root->val > hh->val)
{
root=root->left;
}
}
return root;

}
};
```

## Problem solution in C.

```struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q)
{
struct TreeNode *result = root;

int v1 = p->val, v2 = q->val;
p = q = root;
while (p && q) {
if (p == q) result = p; else break;
if (p->val > v1) p = p->left; else if (p->val < v1) p = p->right; else break;
if (q->val > v2) q = q->left; else if (q->val < v2) q = q->right; else break;
}
return result;
}
```