Lowest Common Ancestor in a BST
You are given a Binary Search Tree (BST) and two nodes $$$p$$$ and $$$q$$$ that exist in the tree. Your task is to find the lowest common ancestor (LCA) of the two nodes.
According to the definition of LCA: "The lowest common ancestor is defined between two nodes $$$p$$$ and $$$q$$$ as the lowest node in the tree that has both $$$p$$$ and $$$q$$$ as descendants (we allow a node to be a descendant of itself)."
You are given the tree in the form of a list of node values, where the list is the level-order traversal of the tree. A value of null represents the absence of a node.
Input Format:
The first line contains a list of values representing the BST in level-order, with null representing missing nodes. Each value is either an integer or the word null.
The second line contains two integers $$$p$$$ and $$$q$$$ — the values of the nodes for which you have to find the lowest common ancestor.
It is guaranteed that:
- All node values in the BST are unique.
- $$$p \ne q$$$.
- $$$p$$$ and $$$q$$$ exist in the BST.
Constraints
- The number of nodes in the tree is in the range $$$[2, 10^5]$$$.
- $$$-10^9 \leq \text{Node.val} \leq 10^9$$$
- All node values are unique.
Output Format:
Print a single integer — the value of the lowest common ancestor of $$$p$$$ and $$$q$$$ in the given BST.
Examples:
Example 1:
Input:
6 2 8 0 4 7 9 null null 3 5 2 8
Output:
6
Example 2:
Input:
6 2 8 0 4 7 9 null null 3 5 2 4
Output:
2
Example 3:
Input:
2 1 2 1
Output:
2
Note:
In the third example, the tree has just two nodes, and the LCA of $$$2$$$ and $$$1$$$ is the root node $$$2$$$.