Algorithmathon Day 11: Binary Search Tree Lowest Common Ancestor
25 July 2013
The Lowest Common Ancestor (LCA) is the node furthest down the tree that is an ancestor of two other nodes. In the tree depicted below the LCA of child nodes 10 and 30 would be 20 and the LCA of 20 and 90 would be 50.
When we first start considering the Lowest Common Ancestor (LCA) problem it is quite natural for it to seem quite difficult. One might start considering searching for each child node while keeping an ancestor list. The better solution turns out to be quite simple. Up until now we have been writing algorithms to solve problems in spite of the data structure. This time the nature of a Binary Search Tree (BST) itself will help us solve the problem. We know that the right side numbers are the larger numbers and the left side is the smaller numbers. It turns out that the LCA will be the first node that is between our two numbers.

Get the root node

Find the current node value

If both child values are less than the current node value goto step 2 with the lesser/left child node as the target

If both child values are greater than the current node value goto step 2 with the greater/right child node as the target

Otherwise the current node is the LCA
Armed with this knowledge we can write our tests and follow it with our code.
# code omitted here
it "should have method 'lowest_common_ancestor'" do
BinarySearchTree.method_defined?(:lowest_common_ancestor).should be_true
end
# code omitted here
it "should not return nil with 'lowest_common_ancestor(10,30)' is called" do
@tree.lowest_common_ancestor(10,30).should_not be_nil
end
it "should return 20 with 'lowest_common_ancestor(10,30)' is called" do
@tree.lowest_common_ancestor(10,30).should == 20
end
it "should return 50 with 'lowest_common_ancestor(20,90)' is called" do
@tree.lowest_common_ancestor(20,90).should == 50
end
it "should return 150 with 'lowest_common_ancestor(130,180)' is called" do
@tree.lowest_common_ancestor(130,180).should == 150
end
# code omitted here
# code omitted here
def lowest_common_ancestor(first_number, second_number)
lowest_common_ancestor_by_recursion(@root,first_number, second_number)
end
# code omitted here
def lowest_common_ancestor_by_recursion(current_node,first_number, second_number)
unless current_node.nil?
if current_node.data > first_number && current_node.data > second_number
lowest_common_ancestor_by_recursion(current_node.lesser,first_number, second_number)
elsif current_node.data < first_number && current_node.data < second_number
lowest_common_ancestor_by_recursion(current_node.greater,first_number, second_number)
else
current_node.data
end
end
end
# code omitted here
Tomorrow we will start String manipulation.