Saturday, September 3, 2011

Compute the LCA for a BST

I really like this problem because it's an interesting application of recursion and it shows your attitude to code paying attention to the details.

A BST is a binary tree where the value stored in the left child is less than the value of the current node, which in turn is less than the value of the right child. This would allow to search for the LCA (lowest common anchestor) by leveraging the structure of the tree.

You visit the current node, if it's value v_current is within the range [v1, v2] and you are looking for v=LCA[n1, n2] then you return the value v  otherwise you move recursively left ( right ) down in the tree according if v_current < n1 < n2 (n1 < n2 < v_current, respectively)

here the code

No comments:

Post a Comment