Tree Binary Tree Binary Search Tree Breadth First Search Depth First Search
Intermediate Level

Implement the lowestCommonAncestorBst method that returns the lowest common ancestor value in a binary search tree.

The input contains a binary search tree, its size, and two node values p and q.

Your task is to return the value of the lowest common ancestor of p and q. The lowest common ancestor is the deepest node that has both values in its subtree, including a node being an ancestor of itself.

For example, in the BST [6,2,8,0,4,7,9], the lowest common ancestor of 2 and 8 is 6.

Example 1
Input:
tree (int[]) = [6,2,8,0,4,7,9]
size (int) = 7
p (int) = 2
q (int) = 8
Return:
(int) 6
Example 2
Input:
tree (int[]) = [6,2,8,0,4,7,9]
size (int) = 7
p (int) = 2
q (int) = 4
Return:
(int) 2
Example 3
Input:
tree (int[]) = [2,1]
size (int) = 2
p (int) = 2
q (int) = 1
Return:
(int) 2

Use the ordering property of a binary search tree.

If both p and q are smaller than the current node, the answer must be in the left subtree. If both are greater, the answer must be in the right subtree.

When the current node lies between p and q, or matches one of them, it is the split point and therefore the lowest common ancestor.

Pseudocode:

function lowestCommonAncestorBst(tree, size, p, q):
    index = 0
    while index < size and tree[index] exists:
        value = tree[index]
        if p < value and q < value:
            index = 2 * index + 1
        else if p > value and q > value:
            index = 2 * index + 2
        else:
            return value
    return -1
Run your code to see the result.