235. Lowest Common Ancestor of a Binary Search Tree

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.left = None
 6#         self.right = None
 7
 8
 9class Solution:
10    def lowestCommonAncestor(
11        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
12    ) -> "TreeNode":
13        # idea: BST
14        n0, n1 = min(p.val, q.val), max(p.val, q.val)
15        if n0 <= root.val <= n1:
16            return root
17        elif n1 < root.val:
18            return self.lowestCommonAncestor(root.left, p, q)
19        return self.lowestCommonAncestor(root.right, p, q)