Posted on by Kalkicode
Code Circular Linked List

Convert a binary tree into a circular doubly linked list in kotlin

Kotlin program for Convert a binary tree into a circular doubly linked list. Here problem description and explanation.

/* 
  Kotlin program for
  Convert binary tree to circular doubly linked list
*/
// Binary Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	// Reversibly converting a given tree to
	// Circular doubly linked list
	fun changeLink(node: TreeNode ? , 
                   l : TreeNode ? , 
                   r : TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Visit left subtree with left and right node
			this.changeLink(node.left, l, node);
			// Visit right subtree with left and right node
			this.changeLink(node.right, node, r);
			if (node.left == null)
			{
				// Set new leaf side node
				node.left = l;
				if (l != null)
				{
					// Because circular doubly linked list
					// So setup right side node
					l.right = node;
				}
			}
			if (node.right == null)
			{
				node.right = r;
				if (r != null)
				{
					// So setup left side node
					r.left = node;
				}
			}
		}
	}
	// Handles the request of convert binary tree into
	// Circular doubly linked list
	fun convertToCll(): Unit
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Change node link
		this.changeLink(this.root, null, null);
		var temp: TreeNode ? = this.root;
		// Setup first new node
		while (temp?.left != null)
		{
			temp = temp.left;
		}
		// Make new root
		this.root = temp;
		// Find last node
		while (temp?.right != null)
		{
			temp = temp.right;
		}
		// Make circular linked list
		temp?.right = this.root;
		this.root?.left = temp;
	}
	// Display circular linked list elements
	fun displayData(): Unit
	{
		// Get first node
		var temp: TreeNode ? = this.root;
		println("\n Circular List element from front to rear");
		while (temp != null)
		{
			// Display node value
			print("  " + temp.data);
			// Visit to right node
			temp = temp.right;
			if (temp == this.root)
			{
				// Stop execution
				temp = null;
			}
		}
		println("\n Circular List element from rear to front");
		// Get last node
		temp = this.root?.left;
		while (temp != null)
		{
			// Display node value
			print("  " + temp.data);
			// Visit to left node
			temp = temp.left;
			if (temp == this.root?.left)
			{
				// Stop execution
				temp = null;
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create a binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	        -1
	       /   \
	      2     8
	     / \   / \
	    3  -3 6   5
	       /   \   \
	     -7     4  -6
	     /     / \
	    9     1  -2  
	         /
	        7 
	-----------------------
	      Binary Tree
	-----------------------
	*/
	tree.root = TreeNode(-1);
	tree.root?.left = TreeNode(2);
	tree.root?.right = TreeNode(8);
	tree.root?.left?.left = TreeNode(3);
	tree.root?.left?.right = TreeNode(-3);
	tree.root?.left?.right?.left = TreeNode(-7);
	tree.root?.left?.right?.left?.left = TreeNode(9);
	tree.root?.right?.left = TreeNode(6);
	tree.root?.right?.right = TreeNode(5);
	tree.root?.right?.left?.right = TreeNode(4);
	tree.root?.right?.right?.right = TreeNode(-6);
	tree.root?.right?.left?.right?.left = TreeNode(1);
	tree.root?.right?.left?.right?.right = TreeNode(-2);
	tree.root?.right?.left?.right?.left?.left = TreeNode(7);
	// Convert to circular doubly linked list
	tree.convertToCll();
	// Display element
	tree.displayData();
}

Output

 Circular List element from front to rear
  3  2  9  -7  -3  -1  6  7  1  4  -2  8  5  -6
 Circular List element from rear to front
  -6  5  8  -2  4  1  7  6  -1  -3  -7  9  2  3

Comment

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