# Ruby BST code for insertion implementation

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

• 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. – thesecretmaster Dec 26 '17 at 12:03

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