Implement a tree iterator

Question

I created a very simple node class with a name and an array of nodes. I also created an iterator class with a next method that helps me iterate on each node and child nodes. I need to write the next method, but I don't what is the best way to do it.

class Node

  def initialize(name, nodes
    @name = name
    @nodes = nodes
  end
end

class Iterator
  def initialize(node)
    @node = node
  end

  def next
    ???
  end
end

Example:

z = Node.new("z", [])
b = Node.new("b", [z])    
c = Node.new("c", [])
parent = Node.new("a", [b, c]) 

iterator = Iterator.new(parent)
str = ''
next = iterator.next
while next do
 str += next.name
 next = iterator.next
end

str should equal "abzc"

Can anybody help me with this?

In your mind, what does "next" mean? There are two common algorithms for traversing a graph- depth first and bredth first. Question is, when you iterate, do you want to see all nodes in one level before any node in the next level? Or do you want to traverse a branch all the way down to its leaves before moving on to the next branch? Either way, the algorithm involves recursion. Happy to help more if you can elaborate on your requirement. — Kent Rancourt
– Kent Rancourt, Commented May 19, 2012 at 1:43
From the OP example, it looks like depth-first (else str should equal "abcz" instead of "abzc"). — Scott Hunter
– Scott Hunter, Commented May 19, 2012 at 1:55

Kent Rancourt · Accepted Answer · 2014-06-10 17:01:08Z

7

If I may suggest a more idiomatic approach:

class Node

  attr_accessor :name, :children

  def initialize(name, children = [ ])
    @name = name
    @children = children
  end

  def traverse(&block)
    yield self
    @children.each { |child| child.traverse(&block) }
  end

end

z = Node.new("z")
b = Node.new("b", [z])
c = Node.new("c")
parent = Node.new("a", [b, c])

str = ''
parent.traverse { |node| str += node.name }
puts str

This has a benefit over btilly's solution (which is also correct) in that it doesn't proliferate Iterator objects and suck up memory- in fact Iterator disappears from the implementation (while still retaining the ability to DO something to each node in succession). This is more idiomatic; more Ruby-esque.

edited Jun 10, 2014 at 17:01

answered May 19, 2012 at 4:56

Kent Rancourt

1,5951 gold badge12 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Kent Rancourt Over a year ago

@Paul, can you explain perhaps why the next() approach is required? Seems to be a strange requirement since it is at odds with the "ruby way" of doing things.

Scott Hunter · Accepted Answer · 2012-05-19 02:00:56Z

0

In your iterator, if node has any children, next would be the first of them. If it doesn't, then you need to "back up" to the last sibling that you skipped over. This implies that you need to keep track of the siblings that have been skipped over, so that you can go back to them.

answered May 19, 2012 at 2:00

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Comments

btilly · Accepted Answer · 2012-05-19 02:21:39Z

0

Here is some running code that demonstrates what I think you're looking for.

class Node
  attr_accessor :name, :nodes

  def initialize(name, nodes)
    @name = name
    @nodes = nodes
  end
end

class Iterator
  def initialize(node)
    @node = node
  end

  def each_node
    yield @node
    for node in @node.nodes do
      iterator = Iterator.new(node)
      iterator.each_node {|next_node|
        yield next_node
      }
    end
  end
end

z = Node.new("z", [])
b = Node.new("b", [z])
c = Node.new("c", [])
parent = Node.new("a", [b, c])

iterator = Iterator.new(parent)
str = ''
iterator.each_node {|node|
  str += node.name
}
puts str

answered May 19, 2012 at 2:21

btilly

47.8k3 gold badges69 silver badges101 bronze badges

3 Comments

Paul S. Over a year ago

It needs to be recursive. In you code you assume that there is only 2 level depths. For example, Z could have nodes as well.

Paul S. Over a year ago

And I can't use a each_node method. It must be next.

btilly Over a year ago

@PaulS. try running it. My code is recursive. Add in a node below z and it shows up correctly. As for using next, on my ancient ruby 1.8.6 your code snippet broke. If you understand how my code works, you should be able to modify it to work in the way that you want. (Though given that next is a key word in Ruby, it is a poor choice of variable name...)

Esailija · Accepted Answer · 2012-07-11 09:30:44Z

0

I have been able to solve my problem by doing the following. But what I don't like with this approach is that I traverse the nodes during the initialization instead of in the next method...

class Iterator

  def initialize(node)
    @node   = node
    @index  = -1
    @list   = []

    traverse(@node)
  end

  def next
    @index += 1
    @list[@index]
  end

  private
  def traverse(root)
    @list[@list.size] = root
    if root.nodes
      for n in root.nodes do
        traverse(n)
      end
    end  
  end

end

edited Jul 11, 2012 at 9:30

Esailija

140k24 gold badges280 silver badges328 bronze badges

answered May 19, 2012 at 19:22

Paul S.

11 silver badge2 bronze badges

Collectives™ on Stack Overflow

Implement a tree iterator

4 Answers 4

1 Comment

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related