# Java/Python iterative solution

• Python

``````def lowestCommonAncestor(self, root, p, q):
stack = [root]
parent = {root: None}
while p not in parent or q not in parent:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
while p:
p = parent[p]
while q not in ancestors:
q = parent[q]
return q

# 31 / 31 test cases passed.
# Status: Accepted
# Runtime: 108 ms
# 99.14%
``````

Java

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
parent.put(root, null);
stack.push(root);

while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode node = stack.pop();
if (node.left != null) {
parent.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parent.put(node.right, node);
stack.push(node.right);
}
}
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
p = parent.get(p);
}
while (!ancestors.contains(q))
q = parent.get(q);
return q;
}
}
``````

To find the lowest common ancestor, we need to find where is `p` and `q` and a way to track their ancestors. A `parent` pointer for each node found is good for the job. After we found both `p` and `q`, we create a set of `p`'s `ancestors`. Then we travel through `q`'s `ancestors`, the first one appears in `p`'s is our answer.

• Very visual and clear!

• I like this, easy to understand. Thank you for sharing.

• Good idea to build parent map, however when building the map, using a queue by level order is preferred.

• Thank you pepsi! It is straightforward and fast!

• so cool!. learned

• parent dictionary is a really good idea!

• @dietpepsi What is the running time for this solution?

• Another solution is to run DFS for both p and q values and create paths from root to p and q. These paths can be stored in lists. Since we need lowest common ancestor, we can check from the front for the last such node which is common in both the lists.

Running time:
DFS will lead to O(N) since this is a binary tree and not a binary search tree.
Two DFS operations will lead to O(N)
Comparison work of the lists - using a while loop - to find common element will take O(N)
So total running time - O(N)

Space
Lists to store paths can lead to O(N)

• @acheiver Nice analysis. However, I think the worst case for DFS is O(n), where n is the node numbers in the tree. The average case is O(h).

• @sunraincyq Oh yes. You are right. The worst case for DFS is O(h) when the tree is a binary search tree not a binary tree. For a binary tree, it will be O(n)

I have modified my statements.

• Easy to understand and implement. I convert your solution into C++ and post here for other's reference.

``````class Solution {
public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//iterative solution

unordered_map<TreeNode*,TreeNode*> mm;
mm[root]=NULL;
queue<TreeNode*> qq;
qq.push(root);
while(mm.count(p)==0||mm.count(q)==0){
TreeNode* tmp=qq.front();
qq.pop();
if(tmp->left){
mm[tmp->left]=tmp;
qq.push(tmp->left);
}
if(tmp->right){
mm[tmp->right]=tmp;
qq.push(tmp->right);
}
}
unordered_set<TreeNode*> ss;
while(p!=NULL){
ss.insert(p);
p=mm[p];
}
while(ss.count(q)==0){
q=mm[q];
}
return q;
}
};``````

• This post is deleted!

• The idea is great, but I wonder why not use a queue to do BFS. If we use a stack it always traverses the right subtree first.

``````TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
unordered_map<TreeNode*, TreeNode*> parents;
parents[root] = nullptr;
queue<TreeNode*> qu;
qu.push(root);
while (!parents.count(p) || !parents.count(q)) {
int qsize = (int)qu.size();
for (int i = 0; i < qsize; ++i) {
auto node = qu.front();
qu.pop();
if (node -> left) {
parents[node -> left] = node;
qu.push(node -> left);
}
if (node -> right) {
parents[node -> right] = node;
qu.push(node -> right);
}
}
}
unordered_set<TreeNode*> ancestors;
while (p) ancestors.insert(p), p = parents[p];
while (q && !ancestors.count(q)) q = parents[q];
return q;
}
``````

• excellent iterative solution...understood LCA concept through this code

• great and intuitive solution!

• This solution is wow..!!

• Easy to understand . Thank you !

• @garygao1993 I had the same question! Why not a queue?

• @subbrammanian @garygao1993
It doesn't really matter if we're using a `stack` or a `queue`. In this case, all we need is find `p` or `q` during the search, BFS just won't speed up it on average. Besides, writing `stack` only uses two characters `[]` while for `queue` in Python, you need `collections.deque()` which is much longer.

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