Ruby, is this Binary Tree Correct?

welcome to the ruby world! Beware you might really like it and never come back to another language :)

Here are some comments I can give you:

Testing

First thing when you wonder if your code is correct is to test it with different inputs. You can do it by hand, in the console, or you can write tests that will follow you during the development.

By printing

A quick way of testing what you do is to define the to_s method on your Node class. For instance, this will allow to check your tree is ordered:

class Node
  …
  def to_s
     "#{left} #{value} #{right}".strip
  end
end 

to_s is the default ruby method used when converting an object to a string. You can for instance do:

#> puts BinaryTree.new.build_tree([5, 9, 1, 6])
1 5 6 9

By testing

For your peace of mind, you can describe some tests that will allow you to write code, and modify it, and check it is still working. I would suggest minitest for doing it easily.

require 'minitest/autorun'

describe BinaryTree do
  before do
    @constructor = BinaryTree.new
  end

  describe 'when given an array' do
    it 'sorts it' do
      @constructor.build_tree([1, 3, 2]).to_s.must_equal '1 2 3'
    end
  end

  describe 'when given an array with duplicates' do
    it 'builds the correct tree' do
      @constructor.build_tree([1, 3, 2, 3]).to_s.must_equal '1 2 3 3'
    end
  end
end

You can then run it with ruby -Ilib:test binary_tree.rb if binary_tree.rb is the file where you put your code.

You will see there, as you mentioned, that the duplicate code doesn’t work. You can make it work by removing a condition in the if…elsif block.

Then you wan work on the code and run the test as often as you like so that you are confident you didn’t break anything.

Each time you have an edge case you are not sure your code handles, just put that in a test.

Counting the nodes

Your Node.nodes method is probably not what you want if it is supposed to count the number of nodes in your binary tree. It should be in the instance of a Node, not in the class itself: if you have several trees, all nodes are taken into account for each tree.

Ruby things

Some of the things you write could be expressed differently in ruby:

Nil is not necessary

attr_accessor parent is syntactic sugar for

def parent
  @parent
end

def parent=(other)
  @parent = other
end

In ruby if your instance variable @parent is not declared, it has the value nil by default, and calling node.parent will return nil too.

You don’t need these 2 lines in the initializer:

@left = nil
@right = nil

Return is not necessary

When your last instruction in a method is a return, you don’t need the return keyword. That is what I did with the to_s method above.

Named parameters

I think it is cleaner to have named parameters when they are not obvious. For instance, calling Node.new(value, node) doesn’t really help understanding what are these 2 parameters for. I get that a node should have a value, but what is this second parameter?

You could define:

def initialize(value, parent: nil)
  # Same as before
end

and call it with Node.new(value, parent: node), or Node.new(value)

OO things

Moving methods where they belong

Your BinaryTree#add_child method should be on a node. You are adding a child to the node. Move it there, so you don’t need your second parameter: add_child(value, node.right) becomes node.right.add_child(value)

class Node
  ...
  def add_child(other_value)
    if other_value < value
      left.nil? ? self.left = Node.new(other_value, parent: self) : left.add_child(other_value)
    else
      right.nil? ? self.right = Node.new(other_value, parent: self) : right.add_child(other_value)
    end
  end
end

class BinaryTree
  ...
  def add_child(value)
    if @root.nil?
      @root = Node.new(value)
    else
      @root.add_child(value)
    end
    @root
  end
end

While you are there you could also get rid of build_tree in the BinaryTree class, and move it to the Node.

I hope it will help you in your Ruby Journey.