Code Excursion

Algorithmathon Day 10: Pre-order Traversal

Created: 24 July 2013 Modified:

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.

Get the root node
Record the node value
If a lesser node exists goto step 2 with lesser as the target
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()
        @tree.add(BinarySearchTreeNode.new(100))
        @tree.add(BinarySearchTreeNode.new(50))
        @tree.add(BinarySearchTreeNode.new(20))
        @tree.add(BinarySearchTreeNode.new(70))
        @tree.add(BinarySearchTreeNode.new(10))
        @tree.add(BinarySearchTreeNode.new(30))
        @tree.add(BinarySearchTreeNode.new(60))
        @tree.add(BinarySearchTreeNode.new(80))
        @tree.add(BinarySearchTreeNode.new(90))
        @tree.add(BinarySearchTreeNode.new(40))

        @tree.add(BinarySearchTreeNode.new(150))
        @tree.add(BinarySearchTreeNode.new(120))
        @tree.add(BinarySearchTreeNode.new(170))
        @tree.add(BinarySearchTreeNode.new(110))
        @tree.add(BinarySearchTreeNode.new(130))
        @tree.add(BinarySearchTreeNode.new(160))
        @tree.add(BinarySearchTreeNode.new(180))
        @tree.add(BinarySearchTreeNode.new(190))
        @tree.add(BinarySearchTreeNode.new(140))
      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.

tags: Algorithm - Algorithmathon - RSpec - Ruby