find the closest common ancestor of two nodes of a tree

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 -

Elliot

https://www.emikek.com

I'm a .NET, PHP, Python, and Javascript developer. Also Project Manager, Scrum Master, and Juilliard trained violist. You cannot connect with me on Facebook, Twitter, or LinkedIn so don't ask.