1650. Lowest Common Ancestor of a Binary Tree III

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        """
        assuming all node val  are unique 
        tc O(N)  sc O(N)
        """
        seen = set()
        node = p 
        while node:
            seen.add(node.val)
            node = node.parent
        
        cur = q
        while cur:
            if cur.val in seen:
                return cur
            cur = cur.parent 
        return None 

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        """  tc O(H(p)+ H(q))  ==>O(N)   space O(1)
        ### assuming p,q both exist in the tree 
        
        take it like a linkedlist problem:  finding intersection of two linked list 
        tc O(N)  sc O(1)
        assuming q is LCA 
        p            q    root
        |-----x------|--y--|
        
        for q reach to root: distance y  == > set q  as x  +y  when q reach root:  total dis for q: x + 2 y 
        for p reach to root: distance x + y => set p  as y when q reach root:  total dis for p: x + 2 y at this moment, p and q has gone same distance=> pp == qq  
        
        from that on, pp and qq will have same parent node. which will be consider LCA 
        """
        pp,qq = p,q
        #cnt = 0
        while pp != qq:
            cnt += 1 
            pp = pp.parent if pp.parent else q
            qq = qq.parent if qq.parent else p
        #print(cnt)
        return pp