# Slow but correct verson using DFS, but i can't think a faster one

• ``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// find the pathes to the two nodes using dfs,
// then find the last common node along the pathes

stack<TreeNode*> path_p;
stack<TreeNode*> path_q;

bool is_p_found;
bool is_q_found;

stack<TreeNode*> path;

void reverse_stack(stack<TreeNode*> from, stack<TreeNode*> &to)
{
while( !from.empty() )
{
to.push( from.top() );
from.pop();
}
}

void dfs(TreeNode *root, const TreeNode *p, const TreeNode *q)
{
if(is_p_found && is_q_found) return;

if(!root) return;

path.push(root);

if(root == p)
{
reverse_stack(path, path_p);
is_p_found = true;
}
if(root == q)
{
reverse_stack(path, path_q);
is_q_found = true;
}

dfs(root->left, p, q);
dfs(root->right, p, q);

path.pop();
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
if(!p) return q;
if(!q) return p;

is_p_found = false;
is_q_found = false;

dfs(root, p, q);

TreeNode *last_common = root;
while(!path_p.empty() && !path_q.empty())
{
if(path_p.top() != path_q.top())
return last_common;

last_common = path_p.top();

path_p.pop();
path_q.pop();
}

return last_common;
}
};``````

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