# Binary Search Tree in Ruby

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

• 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 ... Oct 21 '14 at 21:38
• Ok, I will update with those. Oct 21 '14 at 21:40
• @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.
– Nic
Jun 24 '15 at 16:06
• I did, let me dig it up. Jun 24 '15 at 16:09
• 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.
– Nic
Jun 24 '15 at 18:46

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

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

• 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. Jun 24 '15 at 22:10
• @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."
– Nic
Jun 24 '15 at 22:19
• 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/… Jun 26 '15 at 14:39
• @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.
– Nic
Jun 26 '15 at 15:49
• 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. Jun 26 '15 at 16:11