I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.
The Problem
A binary search tree is a tree with the ordered property. That is, for every node in the tree with value x, all nodes in the left subtree are < x and all nodes in the right subtree are > x recursively.
So, given a binary search tree (BST) and two values, determine the lowest common ancestor of the two values. That is, tracing up from the values, towards the root, find the lowest node (level wise) they have in common.
For example, given the following tree:
20
/ \
10 30
/ \ / \
5 15 25 35
The Lowest Common Ancestor (LCA) of 5 and 15 is 10. Similarly, the lowest common ancestor of 5 and 35 is 20. Note that the value itself could be it’s own LCA, for example, the LCA of 20 and 35 is 20.
The tree itself is composed of standard nodes that only go down. That is, they have a Left and Right child reference but not a Parent reference. You may use the following as your template for a node class:
public class Node<T>
{
public T Value { get; private set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public Node(T value)
{
Value = value;
}
}
Spoiler Alert!
Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.