Depth First Search

Posted by kev Tue, 27 Nov 2007 19:24:00 GMT

Because I hadn’t implemented DFS in Ruby before, and it’s just so damn easy.

Update: Phillip rightly pointed out in the comments that with the yield at the end, it’s actually post-order traversal, not depth first search per se.

class TreeNode
  attr_reader :name

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

  def add_node(node)
    @children << node

  def each_depth_first
    @children.each do |child|
      child.each_depth_first do |c|
        yield c

    yield self

# root  -  a  -  b
#   \       \ 
#    e - f   c  -  d
#     \
#      g

root ="root")
root.add_node( a ="a"))
a.add_node( b ="b"))
a.add_node( c ="c"))
c.add_node( d ="d"))
root.add_node(e ="e"))
e.add_node(f ="f"))
e.add_node(g ="g"))

root.each_depth_first do |child|

# produces:
# b
# d
# c
# a
# f
# g
# e
# root

Posted in ,  | 3 comments


  1. Avatar Uzytkownik said about 3 hours later:

    > a =“a”) > root.add_node( a =“a”))

    I don’t think the first line is needed ;)

  2. Avatar Philip said about 5 hours later:

    Don’t mean to split hairs, but I think you meant ‘postorder’ search (traversal), not depth-first..

    Depth-first would output root, a,b,c,e,f,g (and would be equally as easy to implement, which was the gist of your post, I think)

  3. Avatar Kevin Clark said about 13 hours later:

    Phillip: Quite right. Long day. Sorry.

    Uzytkownik: Also true.

Comments are disabled