# From dumbest to the coolest in C, four different solutions

• The first solution is quoted from the version-I of the problem.

``````//AC - 24ms;
struct TreeNode* lowestCommonAncestor( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
{
if(!p) return q;
if(!q) return p;
if(!root || root == p || root == q) return root;
struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
struct TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left&&right) return root;
if(!left) return right;
if(!right) return left;
}
``````

Actually we can take advantage of the Binary Search Tree considering its value part to make the process more clear and simple.

``````//AC - 20ms;
struct TreeNode* lowestCommonAncestor( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
{
if(root == NULL || root == p || root == q ||
(root->val > p->val && root->val < q->val) ||
(root->val < p->val && root->val > q->val)) return root; //all the possible cases;
if(root->val > p->val && root->val > q->val) //in the left sub;
return lowestCommonAncestor(root->left, p, q);
else //in the right sub;
return lowestCommonAncestor(root->right, p, q);
}
``````

As we have checked the previous solution, the complexity and redundancy is quite annoying. So let's try to reverse the sequence of the checking and then we get the following terse solution!

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

Of course we can simply convert it to iterative version as follows:

``````struct TreeNode* lowestCommonAncestor3( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
{
while(1)
{
if(p->val<root->val && q->val<root->val) root = root->left;
else if(p->val>root->val && q->val>root->val) root = root->right;
else return root;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.