Least Common Ancestor in a Binary Search Tree

Given a binary search tree (BST) and two integer values p and q, find the lowest common ancestor (LCA) of the two nodes. The least common ancestor is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

The BST satisfies the following property: for any node with value \(x\), all nodes in its left subtree have values less than \(x\) and all nodes in its right subtree have values greater than \(x\), i.e. \(\text{left.val} < x < \text{right.val}\) (whenever the children exist).

Your task is to compute the LCA and output its value.

inputFormat

Input Format:

• Line 1: A space-separated list of strings representing the BST node values in the order they should be inserted. The value 'null' indicates an absent node and should be ignored when inserting into the BST.
• Line 2: Two integers p and q separated by a space.

Note: When inserting values into the BST, ignore any occurrence of 'null'.

outputFormat

Output Format:

Output a single integer representing the value of the lowest common ancestor of the nodes with values p and q.

6 2 8 0 4 7 9 null null 3 5
2 8

6