Lowest Common Ancestor of a Binary Search Tree

Statement

Given a binary search tree with $n$ nodes, your task is to find the lowest common ancestor of two of its nodes, node1 and node2.

The lowest common ancestor of two nodes, node1 and node2, is defined as the lowest node in the binary search tree that has both node1 and node2 as descendants.

By definition, a node is a descendant of itself. For example, if node2 is a descendant of node1, and we know that node1 is a descendant of itself, then node1 will be the lowest common ancestor of node1 and node2.

...