Given a binary search tree and two nodes guaranteed to exist on the tree, find the lowest common ancestor they both share.

My first attempt, which is nÃ¤ive but works, involves visiting the left and right subtree of each node to verify both nodes exist on one of them, then traversing to the side where they both exist, and doing it again until we have a node where you can't find both. The answer is the previous one.

A better solution is to cache the ancestors of each in a couple of lists and compare them. I didn't implement this one yet.

The best solution is to use the special property of binary search trees. If both nodes are less than the current node, go left. If both are more, go right. If it's in the middle, stop. You're done. Cool, huh?

## Leave a comment -