# A review of top solutions

1. Iterative solution. Lca is determined by going up from p and q, if each node has a pointer to parent. So the intuition is to compute the child to parent mapping. The great idea is from @dietpepsi
``````    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
unordered_map<TreeNode*,TreeNode*> parent({{root,NULL}});
stack<TreeNode*> stk({root});
while(!parent.count(p) || !parent.count(q)) {
TreeNode *n = stk.top();
stk.pop();
if(n->left) {
parent[n->left] = n;
stk.push(n->left);
}
if(n->right) {
parent[n->right] = n;
stk.push(n->right);
}
}
unordered_set<TreeNode*> path;
while(p) {
path.insert(p);
p = parent[p];
}
while(!path.count(q)) q = parent[q];
return q;
}
``````

The above solution back tracks from p first and then q. If the lca is low, then it is not very efficient. We can back track from p and q similtaneously instead.

``````        unordered_set<TreeNode*> pp, pq;
while(p||q) {
if(p) {
if(pq.count(p)) return p;
pp.insert(p);
p = parent[p];
}
if(q) {
if(pp.count(q)) return q;
pq.insert(q);
q = parent[q];
}
}
return NULL;
``````
1. Recursion. If p or q is found, return it. If found none, return NULL. If p and q are found in left and right subtree, return root(lca). The great idea is from @StefanPochmann
``````    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root||root==p||root==q) return root;
auto l = lowestCommonAncestor(root->left, p, q);
if(l && l!=p && l!=q) return l;
auto r = lowestCommonAncestor(root->right, p, q);
return !l?r:!r?l:root;
}
``````

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