Last active
July 2, 2020 14:57
-
-
Save ashishmd/0569bd9c130d72e3da5a268613d8fc01 to your computer and use it in GitHub Desktop.
Create a binary tree from an array in ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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