Non-recursive c++ code with considering not both p and q are all in the tree (return NULL)

• Non-recursive implement, return NULL if p, q or both are not in the three.

C++

``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> left_stack;
vector<TreeNode*> right_stack;
TreeNode* node = root;
TreeNode* lca = NULL;
while(node)
{
if(node == p || node == q)
if(lca == NULL)
lca = node;
else
return lca;
left_stack.push_back(node);
node = node->left;
}
while(left_stack.size() > 0)
{
node = left_stack.back();
if(node->right == NULL)
{
left_stack.pop_back();
if(node->left != NULL && node->left == lca)
lca = node;
continue;
}
if(right_stack.size() > 0 && node == right_stack.back())
{
left_stack.pop_back();
right_stack.pop_back();
if(lca != NULL && (node->left == lca || node->right == lca))
lca = node;
continue;
}
if(lca != NULL && (node->left == lca || node->right == lca))
lca = node;
right_stack.push_back(node);
node = node->right;
while(node)
{
if(node == p || node == q)
if(lca == NULL)
lca = node;
else
return lca;
left_stack.push_back(node);
node = node->left;
}
}
return NULL;
}
};``````

• Nice, thanks. I wanted to comment how most of solutions here are implemented with recursion, in which the base case (and further code) looks like this:

``````if(root == NULL){
return NULL;
}
if(root == p || root == q)
{
return root;
}

TreeNode *left = LDA(root->left,p, q);
TreeNode *right = LDA(root->right,p,q);

if(left && right) return root;
return left ? left : right;
``````

According to my understanding, this means that if the LDA for a tree is one of the input nodes itself (either p or q), its subtree will never be explored. Instead, LDA function will just return either p or q, and it wont work for cases when either p or q are not present.

Leetcode should add test cases when either p or q are not present in the three.

Feel free to correct me if I am wrong.

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