# Check if a Binary Search Tree is valid

I've written the following code in Ruby:

class Node
attr_accessor :data, :left, :right

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

def valid?(min=nil, max=nil)
if @left.nil? && @right.nil?
# base case (leaf node)
return false if min && @data < min
return false if max && @data >= max
true # otherwise
else
return false if @left && !@left.valid?(min, @data)
return false if @right && !@right.valid?(@data, max)
true # otherwise
end
end
end


The basic idea is that when you turn left (i.e. recurse into left child), the children should be less than the value of the current node (i.e. you're setting a max = @data limit for the children).

To test it, I did:

root =
Node.new(10,
Node.new(5,
Node.new(2), Node.new(7)),
Node.new(15,
Node.new(8), Node.new(20)))

puts root.valid?.inspect # => false (because 8 isn't between 10 -> 15)


Seems to work for me, but would love any feedback (everything's fair game, including style, etc.)

Having to pass - or even being able to pass - min and max to the method doesn't seem quite right. The arguments are only there for the method's own use when calling "itself" on its child nodes - they're not really part of the class's API. So that smells a bit.

I'd take a different approach, and add an #each method:

def each(&block)
left.each(&block) unless left.nil?
yield data
right.each(&block) unless right.nil?
end


This lets you say root.each { |n| ... } like you would with an array. And it lets you include Enumerable - since all that requires is that your class implements an #each method - giving you a bunch of methods for free. For instance, you might implement #valid? like so:

def valid?
each_cons(2).all? { |a, b| a <= b }
end


And of course, thanks to Enumerable, you can also do things like root.to_a, root.reduce, root.include? and other good stuff.

In all, you get this:

class Node
include Enumerable

attr_accessor :data, :left, :right

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

def each(&block)
left.each(&block) unless left.nil?
yield data
right.each(&block) unless right.nil?
end

def valid?
each_cons(2).all? { |a, b| a <= b }
end
end


• Since you have attr_accessor synthesized methods, use them. Don't access instance variables directly with @... unless you have to. The point is, that if you need to customize access, you can simply swap out the synthesized accessor with a custom one, and no other code has to change, since it'll still be calling the method.
• But speaking of accessors, using attr_accessor can be a bit blunt for the left and right attributes, since it lets anyone, anywhere, set them to something nonsensical, like root.left = "foobar!". That'll break things, since you suddenly have non-Node nodes in your tree. So I'd suggest using attr_readers, but adding your own assignment methods, e.g. def left=(node); ...; end. That'll let you check things before assigning.
• The method in question might be named #sorted? instead. valid? could imply any number of things. Edit: You may actually want to use (a <=> b) <= 0, as that's what used to sort objects, instead of just a <= b.
• Don't bother aligning the = assignment operators like you do in the initializer. Yeah, it's pretty, and I'm often tempted to do the same, but it's a bit of busywork that - if you ever have to change the code - requires you to redo it. I've read through my own commit history on projects and wondered why seemingly unchanged lines showed up in the diff, only to realise I was messing around with the whitespace and confusing future-me.
You can also take a different tack, and use an add/insert/<< or something method to add data to the tree, rather than requiring someone else to create new Nodes. E.g root << 15 would traverse the tree, and find the right place to insert the value, creating a new node to hold it, etc. etc.. That way, you won't really need a valid? method.
• Excellent feedback; each_cons is new to me, so I learned that ... in addition to reading up on Enumerable which I hadn't extended before. Thanks a lot! – FloatingRock Apr 2 '17 at 6:42