# Non recursive solution C++

• my code is dirty. Can anyone give me a good solution with non-recursive?

``````TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr)
return root;
stack<TreeNode*> sta;
vector<TreeNode*> vec;
bool tag1 = false;
bool tag2 = false;
sta.push(root);
TreeNode* lastRoot = root;
while (!sta.empty())
{
root = sta.top();
if (root == p) {
if(tag1 == false && tag2 == false)
vec.push_back(root);
tag1 = true;
}
else if (root == q) {
if (tag2 == false && tag1 == false)
vec.push_back(root);
tag2 = true;
}
if (!tag1 && !tag2)
vec.push_back(root);
if (tag1 && tag2 && find(vec.begin(), vec.end(), root) != vec.end())
return root;

if (lastRoot != root->right)
{
if (lastRoot != root->left) {
if (root->left != nullptr) {
sta.push(root->left);
continue;
}
}
if (root->right != nullptr) {
sta.push(root->right);
continue;
}
}
lastRoot = root;
sta.pop();
}
return nullptr;
}``````

• This is not the fastest solution for this problem.

Should check temp->left(/right) != NULL before assigning it. OR check it in while condition while(!found && temp) to prevent segmentation fault.

``````TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int max = p->val > q->val ? p->val : q->val;
int min = p->val < q->val ? p->val : q->val;
bool found = false;
TreeNode *temp=root;
while(!found){
if(temp->val > max){ temp = temp->left;  }
else if(temp->val < min){ temp = temp->right; }
else {found=true;}
}
return temp;
}
``````

I think the best(runtime) C++ solution so far(2016-02-04 04:07:04 GMT) is 36ms.

• This is not BST.

• This post is deleted!

• ``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || !p || !q) return nullptr;
stack<TreeNode*> stk1, stk2;
findNode(stk1, root, p);
findNode(stk2, root, q);
while(stk1.size() > stk2.size())
stk1.pop();
while(stk1.size() < stk2.size())
stk2.pop();
while(stk1.top() != stk2.top()){
stk1.pop();
stk2.pop();
}
return stk1.top();
}
void findNode(stack<TreeNode*> &stk, TreeNode * root, TreeNode* toFindNode){
TreeNode * pre = nullptr, *cur = root;
while(cur || !stk.empty()){
while(cur){
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
if(cur->right && pre != cur->right)
cur = cur->right;
else{
if(cur == toFindNode) break;
stk.pop();
pre = cur;
cur = nullptr;
}
}
}
};``````

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