Insertion in binary search tree without recursion in ruby

Ruby program for Insertion in binary search tree without recursion. Here more information.

#  Ruby program for
#  iterative insert in binary search tree
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end
end

class BinarySearchTree 
	# Define the accessor and reader of class BinarySearchTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	# insert a element
	def addNode(data) 
		#  Create a new node
		node = TreeNode.new(data)
		if (self.root == nil) 
			#  When adds a first node in bst
			self.root = node
		else
 
			find = self.root
			#  Add new node to proper position
			while (find != nil) 
				if (find.data >= data) 
					if (find.left == nil) 
						#  When left child empty
						#  So add new node here
						find.left = node
						return
					else
 
						#  Otherwise
						#  Visit left sub-tree
						find = find.left
					end

				else
 
					if (find.right == nil) 
						#  When right child empty
						#  So add new node here
						find.right = node
						return
					else
 
						#  Visit right sub-tree
						find = find.right
					end
				end
			end
		end
	end

	#  Display preorder
	def preorder(node) 
		if (node != nil) 
			#  Display node value
			print("  ", node.data)
			#  Visit to left subtree
			self.preorder(node.left)
			#  Visit to right subtree
			self.preorder(node.right)
		end

	end

	def inorder(node) 
		if (node != nil) 
			#  Visit to left subtree
			self.inorder(node.left)
			#  Display node value
			print("  ", node.data)
			#  Visit to right subtree
			self.inorder(node.right)
		end

	end

	def postorder(node) 
		if (node != nil) 
			#  Visit to left subtree
			self.postorder(node.left)
			#  Visit to right subtree
			self.postorder(node.right)
			#  Display node value
			print("  ", node.data)
		end
	end
end

def main() 
	tree = BinarySearchTree.new()
	#         10
	#        / \
	#       /   \
	#      4     15
	#     / \   /
	#    3   5 12
	#    -------------
	#    Build binary search tree
	tree.addNode(10)
	tree.addNode(4)
	tree.addNode(3)
	tree.addNode(5)
	tree.addNode(15)
	tree.addNode(12)
	#  Display tree nodes
	print("Preorder \n")
	tree.preorder(tree.root)
	print("\nInorder \n")
	tree.inorder(tree.root)
	print("\nPostorder \n")
	tree.postorder(tree.root)
end

main()

Output

Preorder 
  10  4  3  5  15  12
Inorder 
  3  4  5  10  12  15
Postorder 
  3  5  4  12  15  10


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved