LC 1650 [M] Lowest Common Ancestor of a Binary Tree III - ALawliet/algorithms GitHub Wiki

here we are only given p, q (x root is missing)

• store the path from p to root
• then check q to root, first node that was already in the p path is the LCA

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

# recursive set method one path at a time: O(n) time, O(n) space
class Solution:
    def lowestCommonAncestor(self, p, q):
        p_path = set()
        def traverse_up(node):
            if not node or node in p_path:
                return node
            p_path.add(node)
            return traverse_up(node.parent)
        
        traverse_up(p) # build p_set
        return traverse_up(q) # will return lowest node (first one found) that was also found in p

        # return traverse_up(p) or traverse_up(q) 

# trick: find the intersection of a linked list both paths at the same time: O(n) time (but faster), O(1) space
# move to next while you can, then switch to the other pointer
class Solution:
    def lowestCommonAncestor(self, p, q):
        _p, _q = p, q # pointers
        while _p != _q:
            _p = _p.parent if _p.parent else q
            _q = _q.parent if _q.parent else p
        return _q # or _p (they are the same)