Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
tr_tree
class Tree
attr_accessor :value, :children
def initialize(value, children = [])
@value = value
@children = children
end
end
def BFS(data, target)
queue = [data]
while (!queue.empty?)
element = queue.shift
return element if element.value == target
puts element.value
element.children.each do |child|
queue << child
end
end
end
def DFS(data, target = 11)
return if data.children.size.nil?
data.children.each do |child|
if child.value == target
return
else
puts child.value
DFS(child)
return
end
end
end
# The "Leafs" of a tree, elements that have no children
fifth_node = Tree.new(5, [])
eleventh_node = Tree.new(11, [])
fourth_node = Tree.new(4, [])
# The "Branches" of the tree
ninth_node = Tree.new(9, [fourth_node])
sixth_node = Tree.new(6, [fifth_node, eleventh_node])
seventh_node = Tree.new(7, [sixth_node])
fifth_node = Tree.new(5, [ninth_node])
# The "Trunk" of the tree
trunk = Tree.new(2, [seventh_node, fifth_node])
puts "Breadth First Search"
BFS(trunk, 11)
puts "Depth First Search"
DFS(trunk)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment