Problem description:

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

1
2
3
4
5
6
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

https://assets.leetcode.com/uploads/2018/12/14/binarytree.png

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

https://assets.leetcode.com/uploads/2018/12/14/binarytree.png

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

Solution:

We have link to parent in this question.
Add nodes to a set starting from p to root. Then start to traverse from q to root, if a node already existed in the set, then it’s the LCA.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        visited = set()
        while p:
            visited.add(p)
            p = p.parent
        
        while q:
            if q in visited:
                return q
            else:
                q = q.parent

This is another solution like detect rings in linked list

1
2
3
4
5
6
7
class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        p1, p2 = p, q
        while p1 != p2:
            p1 = p1.parent if p1.parent else p
            p2 = p2.parent if p2.parent else q
        return p1

time complexity: $O()$
space complexity: $O()$
reference:
related problem: