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