1Node = Struct.new(:value, :left, :right, keyword_init: true) do
 2  def to_s
 3    "(#{value},#{left},#{right})"
 4  end
 5end
 6
 7tree = Node.new(
 8  value: 'A',
 9  left: Node.new(value: 'B'),
10  right: Node.new(
11    value: 'C',
12    left: Node.new(value: 'D'),
13    right: Node.new(value: 'E')
14  )
15)
16
17def pre_order(node)
18  return if node.nil?
19
20  print("#{node.value}")
21  pre_order(node.left)
22  pre_order(node.right)
23end
24
25def in_order(node)
26  return if node.nil?
27
28  in_order(node.left)
29  print("#{node.value}")
30  in_order(node.right)
31end
32
33def post_order(node)
34  return if node.nil?
35
36  post_order(node.left)
37  post_order(node.right)
38  print("#{node.value}")
39end
40
41def level_order(node)
42  q = []
43  q.unshift(node)
44
45  until q.empty?
46    node = q.shift
47    next unless node
48
49    print("#{node.value}")
50    q.unshift(node.left)
51    q.unshift(node.right)
52  end
53end
54
55puts "Tree: #{tree}"
56
57print "DFS"
58print "\n\tpre-order:   "
59pre_order(tree)
60
61print "\n\tin-order:    "
62in_order(tree)
63
64print "\n\tpost-order:  "
65post_order(tree)
66puts
67
68print "BFS"
69print "\n\tlevel-order: "
70level_order(tree)
71puts