Skip to content

Instantly share code, notes, and snippets.

@launchkit-codes
Last active August 29, 2015 14:12
Show Gist options
  • Select an option

  • Save launchkit-codes/505771517f2b65310611 to your computer and use it in GitHub Desktop.

Select an option

Save launchkit-codes/505771517f2b65310611 to your computer and use it in GitHub Desktop.
Getting started with Binary Trees and Ruby
# Example:
#
# 1
# / \
# 2 12
# /
# 4
class Node
attr_accessor :left, :right, :value
def initialize(left, right, value)
@left = left
@right = right
@value = value
end
end
class Tree
def initialize
left = Node.new(nil,nil,2)
right = Node.new(nil,nil,12)
left.left = Node.new(nil,nil,4)
@root = Node.new(left, right, 1)
end
def depth
puts tree_depth(@root)
end
def values
tree_values(@root); puts
end
def max
puts tree_max(@root)
end
def min
puts tree_min(@root)
end
def total
puts tree_total(@root)
end
private
def tree_values(node)
print("#{node.value} ")
tree_values(node.left) unless node.left.nil?
tree_values(node.right) unless node.right.nil?
end
def tree_depth(node)
return 0 if node.nil?
left = tree_depth(node.left) + 1
right = tree_depth(node.right) + 1
if left > right
return left
else
return right
end
end
def tree_max(node)
return 0 if node.nil?
max_left = tree_max(node.left)
max_right = tree_max(node.right)
if max_left > node.value && max_left > max_right
return max_left
elsif max_right > node.value
return max_right
else
return node.value
end
end
def tree_min(node)
return 42 if node.nil?
max_left = tree_min(node.left)
max_right = tree_min(node.right)
if max_left < node.value && max_left < max_right
return max_left
elsif max_right < node.value
return max_right
else
return node.value
end
end
def tree_total(node)
return 0 if node.nil?
return node.value + (tree_total(node.left) + tree_total(node.right))
end
end
puts "Tree nodes values:"; Tree.new.values
puts "Tree depth:"; Tree.new.depth
puts "Tree total:"; Tree.new.total
puts "Tree max value:"; Tree.new.max
puts "Tree min value:"; Tree.new.min
$> ruby my_tree.rb
Tree nodes values:
1 2 4 12
Tree depth:
3
Tree total:
19
Tree max value:
12
Tree min value:
1
$>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment