6
\$\begingroup\$

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 
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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 ... \$\endgroup\$
    – ferada
    Oct 21, 2014 at 21:38
  • \$\begingroup\$ Ok, I will update with those. \$\endgroup\$
    – aarti
    Oct 21, 2014 at 21:40
  • \$\begingroup\$ @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. \$\endgroup\$
    – anon
    Jun 24, 2015 at 16:06
  • \$\begingroup\$ I did, let me dig it up. \$\endgroup\$
    – aarti
    Jun 24, 2015 at 16:09
  • \$\begingroup\$ 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. \$\endgroup\$
    – anon
    Jun 24, 2015 at 18:46

2 Answers 2

1
\$\begingroup\$

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

\$\endgroup\$
0
7
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ 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. \$\endgroup\$
    – aarti
    Jun 24, 2015 at 22:10
  • 1
    \$\begingroup\$ @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." \$\endgroup\$
    – anon
    Jun 24, 2015 at 22:19
  • \$\begingroup\$ 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/… \$\endgroup\$
    – aarti
    Jun 26, 2015 at 14:39
  • \$\begingroup\$ @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. \$\endgroup\$
    – anon
    Jun 26, 2015 at 15:49
  • \$\begingroup\$ 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. \$\endgroup\$
    – aarti
    Jun 26, 2015 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.