Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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).”
Input & Output
Input
bst — a binary tree representing the existing BST.
p — the value of node p as described in the question
q — the value of node q as described in the question
Output
The value of the LCA between nodes p and q
Example
Input
bst = [6,2,8,0,4,7,9,x,x,3,5] p = 2 q = 8
Output
6
Explanation
The ancestors of node p with value 2 are node 2 and node 6.
The ancestors of node q with value 8 are node 8 and node 6.
The lowest common ancestors between these two nodes is 6.