Problem statement

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

Solution

One way to solve this problem is to use so-called euler traversal of tree, which loos like root -> left -> root -> right -> root. Then to find LSA we need to find any indexes in euler traversel (it can be several indexes, we can take any) and find node with smallest depth between them.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        self.arr, self.dep = [], []  #euler path
        def dfs(node, depth):
            self.arr += [node]
            self.dep += [depth]
            for child in filter(None, [node.left, node.right]):
                dfs(child, depth + 1)
                self.arr += [node]
                self.dep += [depth]
            
        dfs(root, 0)
        if p not in self.arr or q not in self.arr: return None
        i1, i2 = self.arr.index(p), self.arr.index(q)
        i1, i2 = min(i1, i2), max(i1, i2)

        return self.arr[min(range(i1, i2), key = lambda x: self.dep[x])]