Leetcode 1650

"""
# 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':
        # find all the P parents
        pParents = set()
        while p:
            pParents.add(p)
            p = p.parent
        
        # find the lowestCommonAncestor
        while q:
            if q in pParents:
                return q
            q = q.parent