25 July 2013

Algorithmathon

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.

1. Get the root node
2. Find the current node value
3. If both child values are less than the current node value goto step 2 with the lesser/left child node as the target
4. If both child values are greater than the current node value goto step 2 with the greater/right child node as the target
5. Otherwise the current node is the LCA

Armed with this knowledge we can write our tests and follow it with our code.

binary_search_tree_spec.rb (excerpt)
``````#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
```
```
binary_search_tree.rb (excerpt)
``````#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.

Less Is More ~ Older posts are available in the archive.