**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:
ancestors.add(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) {
ancestors.add(p);
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.