**Solution 1**

Same algorithm as my recursive solution (look there if you want some explanation), but iterative. I do a post-order traversal with a stack. Each stack element at first is a [node, parent] pair, where parent is the stack element of the node's parent node. When the children of a parent get finished, their results are appended to their parent's stack element. So when a parent gets finished, we have the results of its children/subtrees available (its stack element at that point is [node, parent, resultForLeftSubtree, resultForRightSubtree]).

```
def lowestCommonAncestor(self, root, p, q):
answer = []
stack = [[root, answer]]
while stack:
top = stack.pop()
(node, parent), subs = top[:2], top[2:]
if node in (None, p, q):
parent += node,
elif not subs:
stack += top, [node.right, top], [node.left, top]
else:
parent += node if all(subs) else max(subs),
return answer[0]
```

**Solution 2**

Here I find the paths to p and q and then find the last node where the paths match. I just came up with the path-building technique for this, and I find it quite neat and maybe it could be useful elsewhere.

```
def lowestCommonAncestor(self, root, p, q):
def path(root, goal):
path, stack = [], [root]
while True:
node = stack.pop()
if node:
if node not in path[-1:]:
path += node,
if node == goal:
return path
stack += node, node.right, node.left
else:
path.pop()
return next(a for a, b in zip(path(root, p), path(root, q))[::-1] if a == b)
```

**C++ version of Solution 1**

I don't use C++ much, so maybe there's room for improvement with stuff that I don't know.

```
class Solution {
struct Frame {
TreeNode* node;
Frame* parent;
vector<TreeNode*> subs;
};
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
Frame answer;
stack<Frame> stack;
stack.push({root, &answer});
while (stack.size()) {
Frame *top = &stack.top(), *parent = top->parent;
TreeNode *node = top->node;
if (!node || node == p || node == q) {
parent->subs.push_back(node);
stack.pop();
} else if (top->subs.empty()) {
stack.push({node->right, top});
stack.push({node->left, top});
} else {
TreeNode *left = top->subs[0], *right = top->subs[1];
parent->subs.push_back(!left ? right : !right ? left : node);
stack.pop();
}
}
return answer.subs[0];
}
};
```