Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants, where a node is also considered a descendant of itself.

---

Example 1

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6 because 6 is the lowest node that has both as descendants.

Example 2

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5

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

---

Constraints

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the BST.