Lowest Common Ancestor of a Binary Search Tree — Medium Coding Interview Question

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given values p and q in the BST.

Example

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

Output: 6

Topics: trees, binary-search

Asked by: Amazon, Meta, Microsoft, Google

Time complexity: O(h). Space complexity: O(1).