235. Lowest Common Ancestor of a Binary Search Tree

solution.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

"""
We need to binary search until we find our node p and our node q
  - generate a set of nodes we've seen while looking for p
  - find q
  - as we come back up, check to see if we've seen that node finding p
"""
class Solution:
    def build_seen_nodes(self, node: 'TreeNode', seen: set[int], target_val: int):
        seen.add(node.val)
        if target_val == node.val:
            return
        if target_val < node.val:
            return self.build_seen_nodes(node.left, seen, target_val)
        self.build_seen_nodes(node.right, seen, target_val)
    
    def find_lowest_common(self, node: 'TreeNode', seen: set[int], target_val: int):
        if target_val == node.val:
            return target_val in seen, node

        if target_val < node.val:
            found, lowest_common = self.find_lowest_common(node.left, seen, target_val)
        else:
            found, lowest_common = self.find_lowest_common(node.right, seen, target_val)
        
        if found:
            return found, lowest_common
        return node.val in seen, node

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        p_seen_nodes = set()
        self.build_seen_nodes(root, p_seen_nodes, p.val)
        _, lowest_common = self.find_lowest_common(root, p_seen_nodes, q.val)
        return lowest_common