Insertion in binary search tree without recursion in kotlin

Kotlin program for Insertion in binary search tree without recursion. Here problem description and other solutions.

// Kotlin program for
// iterative insert in binary search tree
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	//insert a element
	fun addNode(data: Int): Unit
	{
		// Create a new node
		val node: TreeNode = TreeNode(data);
		if (this.root == null)
		{
			// When adds a first node in bst
			this.root = node;
		}
		else
		{
			var find: TreeNode ? = this.root;
			// Add new node to proper position
			while (find != null)
			{
				if (find.data >= data)
				{
					if (find.left == null)
					{
						// When left child empty
						// So add new node here
						find.left = node;
						return;
					}
					else
					{
						// Otherwise
						// Visit left sub-tree
						find = find.left;
					}
				}
				else
				{
					if (find.right == null)
					{
						// When right child empty
						// So add new node here
						find.right = node;
						return;
					}
					else
					{
						// Visit right sub-tree
						find = find.right;
					}
				}
			}
		}
	}
	// Display preorder
	fun preorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Display node value
			print("  " + node.data);
			// Visit to left subtree
			this.preorder(node.left);
			// Visit to right subtree
			this.preorder(node.right);
		}
	}
	fun inorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Visit to left subtree
			this.inorder(node.left);
			// Display node value
			print("  " + node.data);
			// Visit to right subtree
			this.inorder(node.right);
		}
	}
	fun postorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Visit to left subtree
			this.postorder(node.left);
			// Visit to right subtree
			this.postorder(node.right);
			// Display node value
			print("  " + node.data);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	/*
	         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
	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







© 2021, kalkicode.com, All rights reserved