Insertion in binary search tree using recursion in scala
Scala program for Insertion in binary search tree using recursion. Here problem description and explanation.
// Scala program for
// Insertion in binary search tree by using recursion
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinarySearchTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Insert a node element
def addNode(node: TreeNode, data: Int): TreeNode = {
if (node != null)
{
if (node.data >= data)
{
// When new element is smaller or
// equal to current node
node.left = addNode(node.left, data);
}
else
{
// When new element is higher to current node
node.right = addNode(node.right, data);
}
// important to manage root node
return node;
}
else
{
return new TreeNode(data);
}
}
// Display preorder
def preorder(node: TreeNode): Unit = {
if (node != null)
{
// Display node value
print(" " + node.data);
// Visit to left subtree
preorder(node.left);
// Visit to right subtree
preorder(node.right);
}
}
def inorder(node: TreeNode): Unit = {
if (node != null)
{
// Visit to left subtree
inorder(node.left);
// Display node value
print(" " + node.data);
// Visit to right subtree
inorder(node.right);
}
}
def postorder(node: TreeNode): Unit = {
if (node != null)
{
// Visit to left subtree
postorder(node.left);
// Visit to right subtree
postorder(node.right);
// Display node value
print(" " + node.data);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinarySearchTree = new BinarySearchTree();
/*
10
/ \
/ \
4 15
/ \ /
3 5 12
-------------
Build binary search tree
*/
tree.root = tree.addNode(tree.root, 10);
tree.addNode(tree.root, 4);
tree.addNode(tree.root, 3);
tree.addNode(tree.root, 5);
tree.addNode(tree.root, 15);
tree.addNode(tree.root, 12);
// Display tree nodes
println("Preorder ");
tree.preorder(tree.root);
println("\nInorder ");
tree.inorder(tree.root);
println("\nPostorder ");
tree.postorder(tree.root);
}
}
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