3
\$\begingroup\$

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.)

\$\endgroup\$
2
\$\begingroup\$

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

Beyond that, your current code looks good, only a few comments:

  • 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.

\$\endgroup\$
  • \$\begingroup\$ @kyrill Good point. But why the attitude? Also, fixed \$\endgroup\$ – Flambino Apr 1 '17 at 22:33
  • \$\begingroup\$ 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! \$\endgroup\$ – FloatingRock Apr 2 '17 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.