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 

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