lowest_common_ancestor_of_a_binary_search_tree 

 1from utils import TreeNode
 2from typing import Optional
 3# @leet start
 4
 5
 6class Solution:
 7    def lowestCommonAncestor(
 8        self, root: Optional[TreeNode], p: TreeNode, q: TreeNode
 9    ) -> Optional[TreeNode]:
10        """
11        To find the least common ancestor of two nodes in a BST, we want to
12        find the node which splits `p` and `q` into different sides of the tree.
13        If `p` and `q` are on the same side of the tree, there is a better LCA to find.
14        So we check the root's value. If it is greater than both `p` and `q`, we go left
15        to find a smaller node value.
16        If it is smaller than both `p` and `q`, we go right to find a smaller node value.
17        If `p` is greater than root and `q` is smaller (or vice-versa) we've found the LCA.
18        Return that node in this case.
19        """
20        if root.val > p.val and root.val > q.val:
21            return self.lowestCommonAncestor(root.left, p, q)
22        elif root.val < p.val and root.val < q.val:
23            return self.lowestCommonAncestor(root.right, p, q)
24        return root
25
26
27# @leet end
28
29
30def test():
31    assert 2 + 2 == 4
class Solution: 
 7class Solution:
 8    def lowestCommonAncestor(
 9        self, root: Optional[TreeNode], p: TreeNode, q: TreeNode
10    ) -> Optional[TreeNode]:
11        """
12        To find the least common ancestor of two nodes in a BST, we want to
13        find the node which splits `p` and `q` into different sides of the tree.
14        If `p` and `q` are on the same side of the tree, there is a better LCA to find.
15        So we check the root's value. If it is greater than both `p` and `q`, we go left
16        to find a smaller node value.
17        If it is smaller than both `p` and `q`, we go right to find a smaller node value.
18        If `p` is greater than root and `q` is smaller (or vice-versa) we've found the LCA.
19        Return that node in this case.
20        """
21        if root.val > p.val and root.val > q.val:
22            return self.lowestCommonAncestor(root.left, p, q)
23        elif root.val < p.val and root.val < q.val:
24            return self.lowestCommonAncestor(root.right, p, q)
25        return root
def lowestCommonAncestor( self, root: Optional[utils.TreeNode], p: utils.TreeNode, q: utils.TreeNode) -> Optional[utils.TreeNode]: 
 8    def lowestCommonAncestor(
 9        self, root: Optional[TreeNode], p: TreeNode, q: TreeNode
10    ) -> Optional[TreeNode]:
11        """
12        To find the least common ancestor of two nodes in a BST, we want to
13        find the node which splits `p` and `q` into different sides of the tree.
14        If `p` and `q` are on the same side of the tree, there is a better LCA to find.
15        So we check the root's value. If it is greater than both `p` and `q`, we go left
16        to find a smaller node value.
17        If it is smaller than both `p` and `q`, we go right to find a smaller node value.
18        If `p` is greater than root and `q` is smaller (or vice-versa) we've found the LCA.
19        Return that node in this case.
20        """
21        if root.val > p.val and root.val > q.val:
22            return self.lowestCommonAncestor(root.left, p, q)
23        elif root.val < p.val and root.val < q.val:
24            return self.lowestCommonAncestor(root.right, p, q)
25        return root

To find the least common ancestor of two nodes in a BST, we want to find the node which splits p and q into different sides of the tree. If p and q are on the same side of the tree, there is a better LCA to find. So we check the root's value. If it is greater than both p and q, we go left to find a smaller node value. If it is smaller than both p and q, we go right to find a smaller node value. If p is greater than root and q is smaller (or vice-versa) we've found the LCA. Return that node in this case.

def test(): 
31def test():
32    assert 2 + 2 == 4