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.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Class TreeNode:
    val (int)
    left (TreeNode)
    right (TreeNode)

Input Format:

First Parameter - root of the tree.
Second Parameter - value of the first node p.
Third Parameter - value of the second node q.

Output Format:

Return the lowest common ancestor of the two nodes.

Example 1:

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.

Example 2:

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, since a node can be a descendant of itself according to the LCA definition.

Example 3:

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

Constraints:

• The number of the nodes is in the range [2,10⁵].
• -10⁹ <= node.val <= 10⁹.
• All node.val are unique.
• p!=q.
• p and q will exist in the BST.
• Expected Time Complexity: O(h), where h is the height of the BST.
• Expected Space Complexity: O(1).