### Question

Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.

**Note:**

This is Part II of Lowest Common Ancestor of a Binary Tree. If you need to find the lowest common ancestor without parent pointers, please read Lowest Common Ancestor of a Binary Tree Part I.

_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4

If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

In my last post: Lowest Common Ancestor of a Binary Tree Part I, we have devised a recursive solution which finds the LCA in O(*n*) time. If each node has a pointer that link to its parent, could we devise a better solution?

**Hint:**

No recursion is needed. There is an easy solution which uses extra space. Could you eliminate the need of extra space?

### Analysis

**If have parent pointer, we do not wish to use extra space for the solution**.

- Find the height of both nodes (from the head)
- By calculating the height difference, move the lower nodes up (follow the parent path) to the same level as the other node.
- Two nodes move up together until they meet.
- This solution requires no extra space.

Here is **a very similar question: Intersection of 2 LinkedList**.

### Code

```
// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
int h1 = getHeight(p);
int h2 = getHeight(q);
// swap both nodes in case p is deeper than q.
if (h1 > h2) {
swap(h1, h2);
swap(p, q);
}
// invariant: h1 <= h2.
int dh = h2 - h1;
for (int h = 0; h < dh; h++)
q = q->parent;
while (p && q) {
if (p == q) return p;
p = p->parent;
q = q->parent;
}
return NULL; // p and q are not in the same tree
}
int getHeight(Node *p) {
int height = 0;
while (p) {
height++;
p = p->parent;
}
return height;
}
```