Posted on by Kalkicode
Code Binary Tree

Convert given binary tree to doubly linked list in node js

Js program for Convert given binary tree to doubly linked list. Here problem description and other solutions.

/* 
  Node JS program for
  Convert a given binary tree to doubly linked list
*/
// Binary Tree Node
class LinkNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	// Display node element of doubly linked list
	display()
	{
		if (this.root == null)
		{
			console.log("Empty Linked List");
		}
		else
		{
			console.log("Linked List Head to Tail :");
			// Get first node of linked list
			var temp = this.root;
			var tail = null;
			// iterate the linked list
			while (temp != null)
			{
				tail = temp;
				// Display node value
				process.stdout.write("  " + temp.data);
				// Visit to next node
				temp = temp.right;
			}
			console.log("\nLinked List Tail to Head :");
			// Get last node of linked list
			temp = tail;
			// iterate the linked list
			while (temp != null)
			{
				// Display node value
				process.stdout.write("  " + temp.data);
				// Visit to prev node
				temp = temp.left;
			}
		}
	}
	// Function which is convert binary tree to DLL
	transform(node, x, y)
	{
		if (node != null)
		{
			// Visit to left subtree
			this.transform(node.left, x, node);
			if (this.root == null)
			{
				// Set the root node when is empty
				this.root = node;
			}
			// Visit to right subtree
			this.transform(node.right, node, y);
			if (node.left == null)
			{
				// Connect left node
				node.left = x;
				if (x != null)
				{
					// Connect right to left node
					x.right = node;
				}
			}
			if (node.right == null)
			{
				// Connect right node
				node.right = y;
				if (y != null)
				{
					// Connect left to right node
					y.left = node;
				}
			}
		}
	}
	doublyList()
	{
		var node = this.root;
		if (node != null)
		{
			// Reset the root value
			this.root = null;
			// Covert into Doubly linked list
			this.transform(node, null, null);
		}
	}
}

function main()
{
	// Create new tree
	var tree = new BinaryTree();
	/*
	  Binary Tree
	-----------------------
	        1
	       /  \
	      2    3
	     /    /  \
	    4    5    6
	     \    \
	      7    9
	     / 
	    8
	*/
	// Add binary tree nodes
	tree.root = new LinkNode(1);
	tree.root.left = new LinkNode(2);
	tree.root.right = new LinkNode(3);
	tree.root.right.right = new LinkNode(6);
	tree.root.right.left = new LinkNode(5);
	tree.root.right.left.right = new LinkNode(9);
	tree.root.left.left = new LinkNode(4);
	tree.root.left.left.right = new LinkNode(7);
	tree.root.left.left.right.left = new LinkNode(8);
	tree.doublyList();
	tree.display();
}
// Start program execution
main();

Output

Linked List Head to Tail :
  4  8  7  2  1  5  9  3  6
Linked List Tail to Head :
  6  3  9  5  1  2  7  8  4

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