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.

Constraints:

• $2 \leq n \leq 500$
• $-10^3 \leq$ Node.data $\leq 10^3$
• All Node.data are unique.
• node1 $\neq$ node2
• node1 and node2 exist in the tree.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Implement your solution in the following coding playground.