Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
# https://zvkemp.github.io/blog/2014/04/25/binary-search-trees-in-ruby/
module BinaryTree
class EmptyNode
def to_a
[]
end
def include?(*)
false
end
def push(*)
false
end
alias_method :<<, :push
def inspect
"{}"
end
end
class Node
# our three features:
attr_reader :value
attr_accessor :left, :right
def initialize(v)
@value = v
@left = EmptyNode.new
@right = EmptyNode.new
end
def push(v)
case value <=> v
when 1 then push_left(v)
when -1 then push_right(v)
when 0 then false # the value is already present
end
end
alias_method :<<, :push
def include?(v)
case value <=> v
when 1 then left.include?(v)
when -1 then right.include?(v)
when 0 then true # the current node is equal to the value
end
end
def inspect
"{#{value}:#{left.inspect}|#{right.inspect}}"
end
def to_a
left.to_a + [value] + right.to_a
end
private
def push_left(v)
left.push(v) or self.left = Node.new(v)
end
def push_right(v)
right.push(v) or self.right = Node.new(v)
end
end
end

is it ok if I pack this into a Gem?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment