Is there a better way to traverse an inheritance tree?

I have a method that ascends an inheritance tree and returns the element at the root, progressively yielding the elements if appropriate:

# Finds the root of the hierarchy.
def root
  element = self
  until element.root?
    yield element if block_given?
    element = element.parent
  end
  yield element if block_given?
  element
end

# Walks the inheritance tree, yielding each element from self to #root.
alias until_root root

If I have a hierarchy like:

1 > 2 > 3

3.root should return 1 and 3.until_root &block should yield 3, then 2, then 1, and finally return 1.

The line which yields elements appears twice in order to yield the actual root element, something I would've liked to accomplish inside the loop.

How can I improve this algorithm?

One way to only have one yield statement would be to recursion instead of a loop:

def root(&blk)
  yield self if blk
  if root?
    self
  else
    parent.root(&blk)
  end
end

Of course the usual caveats regarding recursion in ruby apply, so this isn't necessarily a good idea: It is somewhat expensive and can lead to stack overflows if you recurse deep enough (though it's rather unlikely, you'd encounter a tree deep enough to reach that limit).

Unrelated to this, the name until_root seems somewhat clunky to me. I would recommend each_ancestor instead. In fact I think it would be good idea to have the method return an enumerable of ancestors when no block is given. Then it could just be called ancestors. Of course that would require separating ancestors and root into two separate methods. root could then just be defined as ancestors.last:

# Returns an Enumerable containing the ancestors of this node, starting with
# the node itself and ending with the root.
# If a block is supplied, each ancestor will be yielded to the block instead
# of returning an enumerable.
def ancestors
  return enum_for(:ancestors) unless block_given?

  element = self
  until element.root?
    yield element
    element = element.parent
  end
  yield element
end

def root
  ancestors.last
end

If you do it that way, you can also leave out the if block_given? part of the yield statements because it will return early when no block was given.

As a matter of fact, you can now remove the second yield completely by changing the loop to loop while element is not nil instead of until the root is reached (assuming element.parent will return nil if the element is the root):

def ancestors
  return enum_for(:ancestors) unless block_given?

  element = self
  while element
    yield element
    element = element.parent
  end
end

StackExchange Code Review Q#7982, answer score: 3