Created
June 15, 2010 14:27
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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