Using Comparable Mixin in Binary Search Tree Node Methods

Question

I am implementing a Binary Search Tree using Ruby. I implemented a comparable mixin to conveniently compare Node objects within the tree (compares the data attribute), however I am finding a NoMethodError when the "leaf?" method is being called: <=>': undefined method 'data' for nil:NilClass (NoMethodError)

Here is my implementation:

# Node Class
class BstNode

include Comparable

attr_accessor :left
attr_accessor :right
attr_reader :data

def initialize(val)
    @data = val
    @left = nil
    @right = nil
end

def <=>(node)
    return self.data <=> node.data
end

def leaf?
    return self.left == nil && self.right == nil
end

end

# Tree Class
class BstTree

attr_accessor :root

def initialize(arr)
    @root = build_tree(arr)
end

def build_tree(arr)
    arr.each.with_index do |val, i|
        if i == 0
            self.root = BstNode.new(arr[i])
        else
            insert_node(val)
        end
    end
    return self.root
end

def insert_node(val, node = self.root)
    
    curr = node
    left = val < curr.data ? true : false

    if curr.leaf?
        if left
            curr.left = BstNode.new(val)
        else
            curr.right = BstNode.new(val)
        end
    elsif curr.left == nil && left
        curr.left = BstNode.new(val)
    elsif curr.right == nil && !left
        curr.right = BstNode.new(val)
    else
        return left ? insert_node(val, curr.left) : insert_node(val, curr.right)
    end
    return true
end

end

tree = BstTree.new([4])

puts tree.insert_node(6)
puts tree.insert_node(8)

Any comments or suggestions are appreciated.

Answer 1

Basically Comparable module implements methods like <, <=, ==, >, >=, between? on the object(full list here https://docs.ruby-lang.org/en/2.5.0/Comparable.html) and all of them are basing their functionality of the <=>(space-ship operator).

So when you compare BstNode with nil like BstNode.new(8) == nil the == method will call space-ship operator to resolve the comparison. Because your implementation of it tries to call data method on whatever is passed, it will try to do so even on the nil (equivalent of calling nil.data).

Just add safe navigator(&.) to the space-ship like this, and if think you will be good.

def <=>(node)
    return self.data <=> node&.data
end