[LRUG] Pruning a tree

[Tom Stuart]

On 27 Jun 2011, at 17:32, Andrew Stewart wrote:
> I would like to prune the tree such that the only nodes left are the identified ones and the ones connecting them back to the root.  We ignore any children of identified nodes.

class Node < Struct.new(:value, :children)
  def children
    super || []
  end

  def filter(&predicate)
    filtered_children = children.map { |child| child.filter(&predicate) }.compact
    self.class.new value, filtered_children if !filtered_children.empty? || predicate[value]
  end

  def to_s
    "#{value}#{" -> [#{children.join(', ')}]" unless children.empty?}"
  end
end

--

>> tree = Node.new(2, [Node.new(3, [Node.new(4, [Node.new(5)])]), Node.new(6)])
>> tree.to_s
=> "2 -> [3 -> [4 -> [5]], 6]"
>> tree.filter(&:even?).to_s
=> "2 -> [3 -> [4], 6]"
>> tree.filter(&:odd?).to_s
=> "2 -> [3 -> [4 -> [5]]]"

--

Cheers,
-Tom