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.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
#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.