Algorithmathon Day 11: Binary Search Tree Lowest Common Ancestor

Created: 25 July 2013  Modified:

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.

Binary Tree
Binary Tree

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.

tags: Algorithm - Algorithmathon - Binary Search Tree - RSpec - Ruby
   Less Is More