Problem statement

https://binarysearch.com/problems/Lowest-Common-Ancestor-of-List-of-Values/

Solution

Use dfs to traverse tree, where we keep lvl of node from root. Answer is how many nodes from values we have inside. We are interested in the uppest node, where we have len(s) == total.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root, values):
        s = set(values)
        self.ans = (-1, None)
        def dfs(lvl, node):
            if not node: return 0
            lft = dfs(lvl + 1, node.left)
            rgh = dfs(lvl + 1, node.right)
            total = lft + rgh + int(node.val in s)
            if total == len(s):
                self.ans = max(self.ans, (lvl, node))
            return total
        
        dfs(0, root)
        return self.ans[1]