Skip to main content

Convert given binary tree to doubly linked list in typescript

Ts program for Convert given binary tree to doubly linked list. Here problem description and explanation.

/* 
  TypeScript program for
  Convert a given binary tree to doubly linked list
*/
// Binary Tree Node
class LinkNode
{
	public data: number;
	public left: LinkNode;
	public right: LinkNode;
	constructor(data: number)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	public root: LinkNode;
	constructor()
	{
		// Set initial values
		this.root = null;
	}
	// Display node element of doubly linked list
	public 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: LinkNode = null;
			// iterate the linked list
			while (temp != null)
			{
				tail = temp;
				// Display node value
				console.log("  " + 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
				console.log("  " + temp.data);
				// Visit to prev node
				temp = temp.left;
			}
		}
	}
	// Function which is convert binary tree to DLL
	public transform(node: LinkNode, x: LinkNode, y: LinkNode)
	{
		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;
				}
			}
		}
	}
	public 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);
		}
	}
	public static main(args: string[])
	{
		// 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();
	}
}
BinaryTree.main([]);
/*
 file : code.ts
 tsc --target es6 code.ts
 node code.js
 */

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