Skip to content

Instantly share code, notes, and snippets.

@ashishmd
Last active July 2, 2020 14:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save ashishmd/0569bd9c130d72e3da5a268613d8fc01 to your computer and use it in GitHub Desktop.
Save ashishmd/0569bd9c130d72e3da5a268613d8fc01 to your computer and use it in GitHub Desktop.
Create a binary tree from an array in ruby
# Ruby program to create binary tree from array of numbers
# Class Node to store value, left node and right node
class Node
attr_accessor :value, :left, :right
def initialize(value = nil)
self.value = value
end
end
# Tree class
class BinaryTree
attr_accessor :root
def initialize
self.root = Node.new
end
# Abstracted method to create and
# @param [Array] array: numbers array eg. [1, 2, 3, 4, 5, 6, 6, 6, 6]
def self.create_binary_tree(array)
tree = BinaryTree.new
tree.root = insert_level_order(array, tree.root, 0)
print "In-order traversal: "
tree.in_order_traversal(tree.root)
print "\nPre-order traversal: "
tree.pre_order_traversal(tree.root)
print "\nPost-order traversal: "
tree.post_order_traversal(tree.root)
end
# Function to insert nodes in level order
def self.insert_level_order(array, node, index)
return node if index > array.size
temp = Node.new(array[index])
root = temp
root.left = insert_level_order(array, root.left, index * 2 + 1)
root.right = insert_level_order(array, root.right, index * 2 + 2)
root
end
# This method does in-order traversal and print the tree
def in_order_traversal(root)
return if root.nil?
in_order_traversal(root.left)
print root.value.to_s + ' '
in_order_traversal(root.right)
end
# This method does pre-order traversal and print the tree
def pre_order_traversal(root)
return if root.nil?
print root.value.to_s + ' '
pre_order_traversal(root.left)
pre_order_traversal(root.right)
end
# This method does post-order traversal and print the tree
def post_order_traversal(root)
return if root.nil?
post_order_traversal(root.left)
post_order_traversal(root.right)
print root.value.to_s + ' '
end
end
# calling method to create and print binary tree.
BinaryTree.create_binary_tree([1, 2, 3, 4, 5, 6, 6, 6, 6])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment