Skip to content

Instantly share code, notes, and snippets.

@trobrock
Created June 15, 2010 14:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save trobrock/439198 to your computer and use it in GitHub Desktop.
Save trobrock/439198 to your computer and use it in GitHub Desktop.
Check to see if a node is part of a binary search tree
class Node
attr_accessor :left, :right, :value
def is_bst?(min = -1.0/0, max = 1.0/0)
# exit if the siblings are not of the Node type or Nil and have valid value
return false unless is_valid?
return false unless left.nil? or left.is_bst?(min, value)
return false unless right.nil? or right.is_bst?(value, max)
value > min and value < max
end
def is_valid?
# check that the left sibling is nil or of Node type and has a valid value
return false unless (left.nil? or (left.class == Node and (left.value.class == Fixnum or left.value.class == Float)))
# check that the right sibling is nil or of Node type and has a valid value
return false unless (right.nil? or (right.class == Node and (right.value.class == Fixnum or right.value.class == Float)))
# check that this node has a valid value
(value.class == Fixnum or value.class == Float)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment