Lowest Common Ancestor of a BST

Lowest Common Ancestor of a BST

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q 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 we allow a node to be a descendant of itself).

Examples

Example 1:

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6

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

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.

Example 3:

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

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.

Expected Complexity

• Time: O(h) where h is the height of the tree
• Space: O(1) iterative, O(h) recursive