Problem statement

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/

Solution

This is almost the same problem as 1257. All we need to do is traverse node p until we reach root and then traverse again from q and check for the first intersection.

Complexity

Time and space complexity is O(h), where h is the height of the binary tree.

Code

class Solution:
    def lowestCommonAncestor(self, p, q):
        path = {p}
        while p:
            p = p.parent
            path.add(p)
            
        while q not in path:
            q = q.parent
            
        return q