"""
1650
medium
LCA of a binary tree 3

"""


# 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':

        if not q or not p:
            return None


        p_parents = set([p])
        q_parents = set([q])

        while p and p.parent or q and q_parents:
            if p and p.parent:
                p_new = p.parent
                p_parents.add(p_new)
                if p_new in q_parents:
                    return p_new
                p = p.parent
            if q and q.parent:
                q_new = q.parent
                q_parents.add(q_new)
                if q_new in p_parents:
                    return q_new
                q = q.parent

        return None







"""
1650
medium
LCA of a binary tree 3

"""


# 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':

        if not q or not p:
            return None


        p_parents = set([p])
        q_parents = set([q])

        while p and p.parent or q and q_parents:
            if p and p.parent:
                p_new = p.parent
                p_parents.add(p_new)
                if p_new in q_parents:
                    return p_new
                p = p.parent
            if q and q.parent:
                q_new = q.parent
                q_parents.add(q_new)
                if q_new in p_parents:
                    return q_new
                q = q.parent

        return None







1650 medium LCA of a binary tree 3 # Definition for a Node.