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
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