In Part I, I went over using TDD to turn an existing binary tree into an ordered array of integers. Here in Part II we’ll use TDD to build a sorted binary tree from an unsorted array of integers. So, the entire flow will be [unsorted_integers] –> sorted_binary_tree –> [sorted_integers].

Since we’re starting with an array and ending with an array I didn’t see any need to create an instance of BinaryTree each time we use it. Instead I created a class method that will be called as

sorted_array = BinaryTree.sort(unsorted_array)

Let’s write a test as well as the method signature. Run the code and see a failing test.

# binary_tree_sort_test.rb
  def test_nil
    assert nil, BinaryTree.sort(nil), 'Should return nil on nil input'
  end

#binary_tree_sort.rb
  def self.sort(ary)
  end

Let’s return nil from our method to get a passing test.

#binary_tree_sort.rb
  def self.sort(ary)
    nil
  end

We got an edge case out of the way. Let’s add another test.

# binary_tree_sort_test.rb
  def test_ary_of_n_1
    assert [1], BinaryTree.sort([1]), 'Should return array of n=1 unchanged'
  end

Test fails. Modify to pass.

#binary_tree_sort.rb
  def self.sort(ary)
    ary
  end

Pass. Again, we KNOW this is the wrong answer, but it’s the simplest answer to make our tests pass. Since we know it’s not the final goal we need to write another test.

# binary_tree_sort_test.rb
  def test_ary_of_n_1
    assert [1], BinaryTree.sort([1]), 'Should return array of n=1 unchanged'
    assert [7], BinaryTree.sort([7]), 'Should return array of n=1 unchanged'
  end

Still passes. Time to make the test array bigger.

# binary_tree_sort_test.rb
  def test_ary_of_n_2
    assert [1, 7], BinaryTree.sort([1, 7]), 'Should return sorted array of n=2 sorted'
  end

Passes again but we haven’t introduced the binary tree yet. Let’s do that and we’ll see that the code starts to get messier

  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary[0], nil, nil) if ary.count == 1
    btree = BinaryTree.new(ary[0], nil, BinaryTree.new(ary[1], nil, nil) )
    return btree.to_a
  end

This still passes but it’s not very pretty. We add another test.

# binary_tree_sort_test.rb
  def test_ary_of_n_2
    assert [1, 7], BinaryTree.sort([1, 7]), 'Should return sorted array of n=2 sorted'
    assert [1, 7], BinaryTree.sort([7, 1]), 'Should return unsorted array of n=2 sorted'
  end

And this, of course fails. The array wasn’t sorted.

Expected: [1, 7]
Actual: [7, 1]

Let’s add a conditional statement to our code to get the second integer onto the correct branch.

# binary_tree_sort.rb
  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary[0], nil, nil) if ary.count == 1
    if ary[0] > ary[1]
      btree = BinaryTree.new(ary[0], BinaryTree.new(ary[1], nil, nil), nil)
    else
      btree = BinaryTree.new(ary[0], nil, BinaryTree.new(ary[1], nil, nil))
    end

    return btree.to_a
  end

It passes again, but it’s really looking like a mess. However, we can see two things – 1. We are going to need a recursive function as we have btrees nested in btrees. 2. We are going to need a conditional statement to determine where to put child branches.
Let’s do some minor refactoring. I know the first item in the ary is going to be at the top of the btree and I know I won’t need it again. If I shift it off the array I can easily access the next item without indexing. Next, I recognize that as long as there are numbers left in my array I need to add a branch to the btree so I wrap the if/else/end statement in an unless ary.count == 0. I can then add the next integer as a btree node on the appropriate side using the left and right methods.

# binary_tree_sort.rb
  def self.sort(ary)
    return nil if ary.nil?
    
    btree = BinaryTree.new(ary.shift, nil, nil)

    unless 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

It passes. Let’s add more tests.

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

This still passes. We’re good on 2 integer arrays. Let’s try 3.

# binary_tree_sort_test.rb
  def test_btree_sort_ary_n_3
    assert_equal [4, 7, 15], BinaryTree.sort([7, 4, 15])
  end

# outcome
Expected: [4, 7, 15]
Actual: [4, 7]

Fail. Of course, we’ve only set up our btree to add 2 branches. Change our unless statement to

      until ary.count == 0

to create a loop and our test passes. Add another test to try to break it with integers in a different order.

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

#outcome
Expected: [7, 14, 15]
Actual: [7, 15]

We have a failing test and can look through our method and see why. The 14 was placed on the right of the 7, then it was replaced with the 15. We need to go deeper to find the correct node. This method is starting to do a lot of things so it makes sense to create a new method with the sole responsibility of adding a node in the right place. From inside our unless loop we will call

      btree.add_node(ary.shift)

In Part III we’ll factor out that method and finish up the algorithm. In the meantime, keep adding tests and making them to pass.