Technical Interview Question: Lowest Common Ancestor of a Binary Search Tree

Question:

Write a function to find the lowest common ancestor (LCA) of two nodes in a Binary Search Tree (BST). The function should take the root node of the BST and the values of the two nodes as input and return the value of the lowest common ancestor.

Input:

• root: The root node of the Binary Search Tree
• value1: Value of the first node
• value2: Value of the second node

Output:

• The value of the lowest common ancestor of the two nodes

Example:

Input:
      6
     / \
    2   8
   / \ / \
  0  4 7  9
    / \
   3   5

Lowest Common Ancestor of 2 and 8: 6
Lowest Common Ancestor of 2 and 4: 2
Lowest Common Ancestor of 2 and 5: 2

Answer:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def lowestCommonAncestor(root, value1, value2):
    if root.value > value1 and root.value > value2:
        return lowestCommonAncestor(root.left, value1, value2)
    elif root.value < value1 and root.value < value2:
        return lowestCommonAncestor(root.right, value1, value2)
    else:
        return root.value

Explanation:

1. Define a TreeNode class to represent the nodes in the binary search tree.
2. Define the lowestCommonAncestor function, which takes the root node of the BST and the values of the two nodes as input.
3. If the value of the root node is greater than both value1 and value2, then the LCA will be in the left subtree. Recur for the left subtree.
4. If the value of the root node is less than both value1 and value2, then the LCA will be in the right subtree. Recur for the right subtree.
5. If neither of the above conditions is true, then the root node itself is the LCA. Return the value of the root node.

The time complexity of this solution is O(h), where h is the height of the BST. The space complexity is O(1) for the iterative solution and O(h) for the recursive solution, due to the function call stack.