Lowest Common Ancestor of a Binary Tree

lcpy gen -n 236   # by problem number
lcpy gen -s lowest_common_ancestor_of_a_binary_tree   # by problem name

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Input: root = [1,2], p = 1, q = 2
Output: 1

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(h)
    def lowest_common_ancestor(
        self, root: TreeNode[int], p: TreeNode[int], q: TreeNode[int]
    ) -> TreeNode[int]:
        result = self._lca(root, p, q)
        assert result is not None
        return result

    def _lca(
        self, root: TreeNode[int] | None, p: TreeNode[int], q: TreeNode[int]
    ) -> TreeNode[int] | None:
        if root in (p, q) or not root:
            return root

        left = self._lca(root.left, p, q)
        right = self._lca(root.right, p, q)

        if left and right:
            return root
        return left or right