Binary Search Tree in Ruby

Question

Binary Search Tree, with preorder traverse. What other methods should I add? How can I improve it?

class Bst

  attr_accessor :data, :left, :right

  def initialize(data)
    self.data = data
  end

  def insert(data)
    if  self.data < data
      if (self.right ) 
        self.right.insert(data)
      else  
        self.right = Bst.new(data)
      end  
    else
      if (self.left ) 
        self.left.insert(data)
      else  
        self.left = Bst.new(data)
      end  
    end      
  end

  def each(&blk)
    Bst.traverse_preorder(self,&blk)
  end

  def self.traverse_preorder(node, &blk)
    return unless node
    traverse_preorder(node.left,&blk) 
    blk.call(node.data)
    traverse_preorder(node.right,&blk)    
  end  

end 

Answer 1

That's not a pre-order traversal; that's an in-order traversal.

Answer 2

Note: Each tip assumes you followed all of the ones before.

There are a bunch of trailing whitespace characters. Get rid of 'em. They're ugly.

Bst is a terrible class name. It means nothing out-of-context, and out-of-context is where it will be. I'd recommend renaming to BinarySearchTree.

In the if statements, there's sometimes an extra space before the close-paren but not after the open; I've only ever seen both or neither. Personally, I would just get rid of the parentheses entirely -- they're unnecessary.

Prefer if obj.nil? over unless obj. It makes it much clearer that it's checking the existence of an object, rather than, say, the result of a method called obj.

Prefer @data to self.data. It functions the same but it's far more standard to directly access instance variables, unless accessing it requires some guard clauses or the like. Ditto for self.right and self.left. The exception is when you're accessing the class from outside, in which case you obviously don't have direct access to instance variables.

Put a space after (but not before) commas -- so traverse_preorder(node.left,&blk) becomes traverse_preorder(node.left, &blk).

In that method, I'd recommend changing blk to block, because it makes no sense to shorten it.

With these changes, here's what your code looks like:

class BinarySearchTree
  attr_accessor :data, :left, :right

  def initialize(data)
    @data = data
  end

  def insert(data)
    if @data < data
      if @right.nil?
        @right = BinarySearchTree.new(data)
      else
        @right.insert(data)
      end
    else
      if @left.nil?
        @left = BinarySearchTree.new(data)
      else
        @left.insert(data)
      end
    end
  end

  def each(&block)
    BinarySearchTree.traverse_preorder(&block)
  end

  def self.traverse_preorder(node, &block)
    node.left.traverse_preorder(&block)
    blk.call(node.data)
    node.right.traverse_preorder(&block)
  end
end