Ruby BST code for insertion implementation

Question

After some help in understanding difference why direct assignment with setter methods don't work, here is my code for a simple BST in ruby. Would appreciate your reviews and suggestions to refactor the code.

class Node 
 attr_accessor :value, :left_child, :right_child
 def initialize (value)
 @value = value 
 @left_child = nil 
 @right_child = nil 
 end
end 
class BST 
 attr_accessor :root 
 def initialize
 @root = nil
 end 
 def insert(value, node)
 if self.root == nil 
 self.root = Node.new(value)
 return self.root
 end 
 return self.root if self.root.value == value
 if node.value > value
 p node
 if node.left_child == nil 
 node.left_child = Node.new(value)
 return node
 else 
 insert(value, node.left_child) 
 end 
 else
 if node.right_child == nil 
 node.right_child = Node.new(value)
 return node
 else 
 insert(value, node.right_child) 
 end
 end 
 end 
end 

• thesecretmaster: Would you mind providing some examples of how this class would be used? Maybe some test cases? I can give some comments without them, but it'd be helpful to have them.

Answer 1

I'll be writing this review assuming that BST stands for Binary Search Tree, and that you're only concerned with constructing the tree, not searching through it. With that in mind, let's start:

Node class

First, for the easy part: in your definition of Node#initialize, you've got a space between the method name and the parenthesis initialize (. While ruby read that fine (it'll even work if you take out the parenthesis all together), it's considered best practice to put the parenthesis right up against the method name, so def initialize(value).

Different methods of dealing with the children

Also, you do not need to initialize @left_child and @right_child to nil. Instance variables do not need to be initialized. If you try and manipulate an uninitialized instance variable, it will behave as if it is set to nil. So, you can simply exclude @left_child and @right_child from your Node#initialize method.

However, if you wanted to allow them to be passed in optionally, you can use arguments or parameters with default values. Here's an example of parameters with default values:

def initialize(value, left_child = nil, right_child = nil)
 @value = value
 @left_child = left_child
 @right_child = right_child
end

and here's and example with hash arguments with defaults:

def initialize(value, left_child: nil, right_child: nil)
 @value = value
 @left_child = left_child
 @right_child = right_child
end

I personally prefer the second, because in that case you could easily pass a right_child without the left_child and vise versa. Otherwise, to pass a right_child, you'd need to pass nil for left_child.

Also, you may want to validate that @left_child and @right_child are both Nodes. In that case, you would want to define attr_readers for those variables and not attr_accessors. You would manually define the accessors like so:

def left_child=(left_child)
 if left_child.is_a? Node
 @left_child = left_child
 else
 # Some handling for invalid left children, e.g.
 throw "Invalid left child: #{left_child}"
 end
end

and the same for @right_child. You could even do it for value too! Or, if you wanted to get fancier, you could define a private validate_node method to avoid duplication in left_node= and right_node=:

def left_child=(left_child)
 @left_child = validate_node(left_child)
end
def right_child=(right_child)
 @right_child = validate_node(right_child)
end
private
def validate_node(node)
 if node.is_a? Node
 node
 else
 throw "You've passed an invalid node: #{node}"
 end
end

In case you didn't know, private methods are methods that (without some ruby magic) cannot be called outside of that class. They are private to that class.

Note: (Partially note to self) This probably isn't the fully best way to do this, the validation method should validate behavior rather than class. I should write more about that.

I think that's all for the Node class, so let's move onward!

BST Class

First off, I think that BST isn't that great of a name for this class. I'd go with Tree, because that is what it stores.

Anyways, first thing first: I'd make it possible to pass root to the initializer by making it an argument with a default value:

def initialize(root = nil)
 @root = root
end

Next thing's next: The #insert method!

I notice that you're checking if self.root is nil. In ruby, there's a slightly faster (IIRC) and much more ruby way of doing this: self.root.nil?. It's a neat, built-in nil check. In addition, there's no reason to modify @root using its accessor, you can actually just modify it directly.

Also, I noticed that wherever you return a value, you're either returning the root, or the node that was passed in. I also note that you're always setting the node that was passed in as the root. So, you're actually always comparing to root. With that in mind, here are some little bits of cleanup (incomplete, I'll come back and finish it):

def insert(value, node)
 # When this occurs, it will set @root.value == node.value
 @root = Node.new(value) if @root.nil? 
 return @root if @root.value == value
 if node.value > value
 if node.left_child.nil?
 node.left_child = Node.new(value)
 else 
 insert(value, node.left_child) 
 end
 else
 if node.right_child.nil?
 node.right_child = Node.new(value)
 else 
 insert(value, node.right_child) 
 end
 end
 return node
end

Other notes

Here's an interesting example of how someone else implemented BSTs in ruby