24 July 2013

Algorithmathon

Today’s goal is to build a Depth First Preorder Traversal. This algorithm is where a tree is searched by checking the current node, searching the children to the left and finally searching the children to the right. Following this pattern will search a tree from the outer edges left to right. Day 9’s code will be our starting point and we should only need to build our tree and write the traversal method(s). The algorithm we will follow has the following steps.

1. Get the root node
2. Record the node value
3. If a lesser node exists goto step 2 with lesser as the target
4. If a greater node exists goto step 2 with greater as the target

We should start with an RSpec test to construct and verify our tree structure. A tree that should look like the diagram below.

binary_search_tree_spec.rb (excerpt)
#code omitted here
describe "Verify Depth First Traversal" do
before(:each) do
@tree = BinarySearchTree.new()

end

it "should have a properly constructed tree" do
@tree.root.should_not be_nil
@tree.root.data.should == 100

@tree.root.lesser.should_not be_nil
@tree.root.lesser.data.should == 50

@tree.root.lesser.greater.should_not be_nil
@tree.root.lesser.greater.data.should == 70

@tree.root.lesser.lesser.should_not be_nil
@tree.root.lesser.lesser.data.should == 20

@tree.root.lesser.lesser.lesser.should_not be_nil
@tree.root.lesser.lesser.lesser.data.should == 10

@tree.root.greater.should_not be_nil
@tree.root.greater.data.should == 150

@tree.root.greater.greater.should_not be_nil
@tree.root.greater.greater.data.should == 170

@tree.root.greater.lesser.should_not be_nil
@tree.root.greater.lesser.data.should == 120

@tree.root.greater.greater.greater.should_not be_nil
@tree.root.greater.greater.greater.data.should == 180

@tree.root.greater.greater.greater.greater.should_not be_nil
@tree.root.greater.greater.greater.greater.data.should == 190
end
end
#code omitted here

This test should and does pass without adding any additional code. We now can be confident of the tree structure we will be working with. Now we should add tests to specify what results our traversal should return.

binary_search_tree_spec.rb (excerpt)
#code omitted here
it "should not return nil when 'depth_preorder()' is called" do
@tree.depth_preorder().should_not be_nil
end

it "should not return 19 when 'depth_preorder().length' is called" do
@tree.depth_preorder().length.should == 19
end

it "should return 100 when 'depth_preorder()[0]' is called" do
@tree.depth_preorder()[0].should == 100
end

it "should return 30 when 'depth_preorder()[4]' is called" do
@tree.depth_preorder()[4].should == 30
end

it "should return 90 when 'depth_preorder()[9]' is called" do
@tree.depth_preorder()[9].should == 90
end

it "should return 150 when 'depth_preorder()[10]' is called" do
@tree.depth_preorder()[10].should == 150
end
it "should return 130 when 'depth_preorder()[13]' is called" do
@tree.depth_preorder()[13].should == 130
end

it "should return 170 when 'depth_preorder()[15]' is called" do
@tree.depth_preorder()[15].should == 170
end
#code omitted here

All of these tests will fail and we must write a recursive method to meet these needs. Fortunately Binary Trees lend themselves very well to recursive solutions. The plan is to pass an array into the methods to record the path taken by the algorithm.

binary_search_tree.rb (excerpt)
#code omitted here
def depth_preorder()
return_value=Array.new()
depth_preorder_by_recursion(@root,return_value)
return_value
end
#code omitted here
def depth_preorder_by_recursion(current_node,tracker)
unless current_node.nil?
tracker.push(current_node.data)
unless current_node.lesser.nil?
depth_preorder_by_recursion(current_node.lesser,tracker)
end
unless current_node.greater.nil?
depth_preorder_by_recursion(current_node.greater,tracker)
end
end
end
#code omitted here

With our tests passing now we have successfully written pre-order traversal using recursion. Let’s look into how we would achieve the same results using iteration. It can be very difficult to envision using iteration to solve a problem that so obviously lends itself to recursion.

Unfortunately, because recursion is so intrinsic to the definition of a preorder traversal, you may have trouble finding an entirely different iterative algorithm to use in place of the recursive algorithm. In such a case, the best course of action is to understand what is happening in the recursion and try to emulate the process iteratively Programming Interviews Exposed

This was a very helpful piece of advice and it was much easier to solve the problem while keeping it in mind. Essentially we need to use a stack and loop through nodes emulating recursion. An array will satisfy the need for a stack. The tests and code are below.

binary_search_tree_spec.rb (excerpt)
#code omitted here
it "should not return nil when 'depth_preorder_alt()' is called" do
@tree.depth_preorder_alt().should_not be_nil
end

it "should not return 19 when 'depth_preorder_alt().length' is called" do
@tree.depth_preorder_alt().length.should == 19
end

it "should return 100 when 'depth_preorder_alt()[0]' is called" do
@tree.depth_preorder_alt()[0].should == 100
end

it "should return 30 when 'depth_preorder_alt()[4]' is called" do
@tree.depth_preorder_alt()[4].should == 30
end

it "should return 90 when 'depth_preorder_alt()[9]' is called" do
@tree.depth_preorder_alt()[9].should == 90
end

it "should return 150 when 'depth_preorder_alt()[10]' is called" do
@tree.depth_preorder_alt()[10].should == 150
end
it "should return 130 when 'depth_preorder_alt()[13]' is called" do
@tree.depth_preorder_alt()[13].should == 130
end

it "should return 170 when 'depth_preorder_alt()[15]' is called" do
@tree.depth_preorder_alt()[15].should == 170
end
#code omitted here
binary_search_tree.rb (excerpt)
#code omitted here
def depth_preorder_alt()
return_value=Array.new()
depth_preorder_by_iteration(@root,return_value)
return_value
end
#code omitted here
def depth_preorder_by_iteration(start_node,tracker)
current_node=start_node
the_stack=Array.new()
while !current_node.nil?
tracker.push(current_node.data)
unless current_node.greater.nil?
the_stack.push(current_node.greater)
end
unless current_node.lesser.nil?
the_stack.push(current_node.lesser)
end
current_node=the_stack.pop()
end
end
#code omitted here

On Algorithmathon Day 11 we will be looking into finding the Lowest Common Ancestor of two nodes in a tree.

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