After Part I and Part II we were left with the following code and a failing test – our binary tree placed 7 at the trunk, 14 on the right node then 15 in place of the 14. We need the tree to place the 15 as the right node of the 14 node. We had decided that the best way to do this was to create a separate function for adding nodes which I’ve included as add_node.

# binary_tree_sort.rb
require_relative 'binary_tree_sort_test'

class BinaryTree
  attr_accessor :payload, :left, :right

  def initialize(payload, left, right)
    @payload = payload
    @left = left
    @right = right
  end

  def to_a
    return left.to_a + [payload] + right.to_a
  end

  def add_node(value)
  end

  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary.shift, nil, nil)
    until ary.count == 0
      if ary[0] > btree.payload
        btree.right = BinaryTree.new(ary.shift, nil, nil)
      else
        btree.left = BinaryTree.new(ary.shift, nil, nil)
      end
    end
    return btree.to_a
  end

# binary_tree_sort_test.rb
require 'minitest/autorun'

class Tester < Minitest::Unit::TestCase
  def setup
    @seven = BinaryTree.new(7, nil, nil)
    @five  = BinaryTree.new(5, nil, nil)
    @four  = BinaryTree.new(4, nil, nil)
    @six   = BinaryTree.new(6, nil, @seven)
    @three = BinaryTree.new(3, nil, @six)
    @two   = BinaryTree.new(2, @four, @five)
    @trunk = BinaryTree.new(1, @two, @three)
  end

  def test_btree_to_array
    assert_equal [7], @seven.to_a
    assert_equal [5], @five.to_a
    assert_equal [4], @four.to_a
    assert_equal [6, 7], @six.to_a
    assert_equal [3, 6, 7], @three.to_a
    assert_equal [4, 2, 5], @two.to_a
    assert_equal [4, 2, 5, 1, 3, 6, 7], @trunk.to_a
  end

  def test_btree_nil
    assert_equal nil, BinaryTree.sort(nil)
  end

  def test_btree_sort_ary_n_1
    assert_equal [1], BinaryTree.sort([1])
    assert_equal [7], BinaryTree.sort([7])
  end

  def test_btree_sort_ary_n_2
    assert_equal [1, 7], BinaryTree.sort([1, 7])
    assert_equal [1, 7], BinaryTree.sort([7, 1])
    assert_equal [6, 6], BinaryTree.sort([6, 6])
    assert_equal [-5, 0], BinaryTree.sort([0, -5])
  end

  def test_btree_sort_ary_n_3
    assert_equal [4, 7, 15], BinaryTree.sort([7, 4, 15])
    assert_equal [7, 14, 15], BinaryTree.sort([7, 14, 15])
  end
end

Refactoring with the new method, but no change in functionality gives us

# binary_tree_sort.rb
  def add_node(new_value)
    if new_value > self.payload
      self.right = BinaryTree.new(new_value, nil, nil)
    else
      self.left = BinaryTree.new(new_value, nil, nil)
    end
  end


  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary.shift, nil, nil)
    until ary.count == 0
      btree.add_node(ary.shift)
    end
    return btree.to_a
  end

Sure enough, we get the same failing test as before. We are going to need to go deeper into the btree. It makes sense to define a pointer that refers to the current node and a boolean flag to let us know when we’ve finally placed the node. We know that we should place the new value only into a nil branch, so we’ll check for that.

# binary_tree_sort.rb
  def add_node(new_value)
    placed = false
    current_node = self
    until placed
      if new_value > current_node.payload 
        if current_node.right.nil?
          current_node.right = BinaryTree.new(new_value, nil, nil)
          placed = true
        end
      else
        if current_node.left.nil?
          current_node.left = BinaryTree.new(new_value, nil, nil)
          placed = true
        end
      end
    end
  end

Instead of failing tests, this hangs our program in an infinite loop as there are cases where placed is never set to true. Something has to happen when we can’t place the value and that, of course is that we set the current_node to move down the tree to the branch we just checked.

# binary_tree_sort.rb
  def add_node(new_value)
    placed = false
    current_node = self
    until placed
      if new_value > current_node.payload 
        if current_node.right.nil?
          current_node.right = BinaryTree.new(new_value, nil, nil)
          placed = true
        else
          current_node = current_node.right
        end
      else
        if current_node.left.nil?
          current_node.left = BinaryTree.new(new_value, nil, nil)
          placed = true
        else
          current_node = current_node.left
        end
      end
    end
  end

This code passes our tests and further testing fails to break it. This is our binary tree sort.