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 

• ferada: Well, you could add post- and in-order traversal, a remove method, rebalancing the tree after each operation, methods to get the tree height, item lookup ...
• aarti: Ok, I will update with those.
• anon: @classyhacker Did you ever get around to updating it? I've got a review of what's currently here written up, but I'd like to let you edit everything in first.
• aarti: I did, let me dig it up.
• anon: Hey, I'm gonna post my review now. If you'd like, you can post another question with the updated code and I'll review that as well, but it's been a couple of hours now and I'm getting kinda bored of waiting.

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

• aarti: It's pretty standard to call it BST, I don't think its a bad name. The self vs @ stuff makes sense, I wrote it a while back so I would write it differently now. if parenthesis is subjective, I will choose to leave it in for clarity. I think.nil? is redundant here.
• anon: @classyhacker Really? Well, I'm gonna let you call it whatever, then. I prefer longer, more descriptive names. The if parentheses is subjective, sure, but the style guide most people follow says not to use them. .nil? is definitely redundant, but "It makes it much clearer that it's checking the existence of an object, rather than, say, the result of a method called obj."
• aarti: Also I would leave this is as a class method. Recursive methods, that call themselves are best represented that way cs.cmu.edu/~pattis/15-1XX/15-200/lectures/llrecursion/…
• anon: @500_error Hmm, yes, an article which declares it should be static without explaining why. If you can provide an authoritative source (so not one lesson in a college's course that doesn't explain anything) that explains the reasoning, feel free to link that. Or give a more precise location, instead of expecting that I'll read through a several page article because you say it has some evidence.
• aarti: Java does the same thing, it has a collections class for static methods that docs.oracle.com/javase/6/docs/api/java/util/Collections.html.