# My C++ solution, easy understand

• `````` TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q)	return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;
return left? left : right;
}``````

• clever !! it could also be used to solve LCA in binary tree~~

• if the tree is BST, the time complexity is would be O(n) because this solution doesn't examine the value of nodes( > or < ) , and if the tree is not BST would also be O(n), am I right?
if the values are compared, the time complexity in BST would be O(logn) ??

• @Isabella_s : Yes, you are right. This problem's ideal time complexity of BST will be O(lgn). My solution's time complexity is O(n), so it is more suitable for the general tree.

• ``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> s1;
stack<TreeNode*> s2;
TreeNode* ptr=root;
while(ptr!=NULL)
{
if(p->val>ptr->val)
{
s1.push(ptr);
ptr=ptr->right;
}else if(p->val<ptr->val)
{
s1.push(ptr);
ptr=ptr->left;
}else{
s1.push(ptr);
break;
};
};
ptr=root;
while(ptr!=NULL)
{
if(q->val>ptr->val)
{
s2.push(ptr);
ptr=ptr->right;
}else if(q->val<ptr->val)
{
s2.push(ptr);
ptr=ptr->left;
}else{
s2.push(ptr);
break;
};
};
while(s1.size()>s2.size())
{
s1.pop();
};
while(s1.size()<s2.size())
{
s2.pop();
};
while(s1.top()!=s2.top())
{
s1.pop();
s2.pop();
};
return s1.top();

}
};``````

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