Extract leaves of a binary tree in a doubly linked list in typescript
Ts program for Extract leaves of a binary tree in a doubly linked list. Here mentioned other language solution.
/*
TypeScript program for
Extract leaves of a binary tree in a doubly linked list
*/
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;
public front: LinkNode;
constructor()
{
// Set initial tree root to null
this.root = null;
// This is initial linked list node
this.front = null;
}
// Recursive function
// Display preorder view of binary tree
public preOrder(node: LinkNode)
{
if (node != null)
{
// Print node value
console.log(" " + node.data);
this.preOrder(node.left);
this.preOrder(node.right);
}
}
// Display extract leaves in tree
public printDoublyList()
{
if (this.front == null)
{
console.log("\n Empty Linked List ");
return;
}
console.log("\n Doubly Linked list : ");
// Start to front node
var temp = this.front;
// Iterate Linked list elements
while (temp != null)
{
// Display node value
console.log(" " + temp.data);
// Visit to next node
temp = temp.right;
}
console.log();
}
// Extract leaf nodes in given binary tree and
// added into doubly linked list
public LinkNode extractLeaves(node: LinkNode)
{
if (node != null)
{
if (node.left == null && node.right == null)
{
// Add node at front of linked list
node.right = this.front;
if (this.front != null)
{
// When this is not first node
// Combine left direction
this.front.left = node;
}
this.front = node;
// Returns null value to the previous node child
return null;
}
node.right = this.extractLeaves(node.right);
node.left = this.extractLeaves(node.left);
return node;
}
return null;
}
public static main()
{
// Make new Binary Tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
/ \
6 8
/ \ / \
2 3 7 5
/ \ \
9 -6 13
*/
// Add nodes
tree.root = new LinkNode(10);
tree.root.left = new LinkNode(6);
tree.root.left.left = new LinkNode(2);
tree.root.right = new LinkNode(8);
tree.root.right.right = new LinkNode(5);
tree.root.right.left = new LinkNode(7);
tree.root.right.left.right = new LinkNode(-6);
tree.root.left.right = new LinkNode(3);
tree.root.left.left.left = new LinkNode(9);
tree.root.right.right.right = new LinkNode(13);
// Display tree elements
console.log("\n Preorder : ");
tree.preOrder(tree.root);
tree.extractLeaves(tree.root);
// After transform
console.log("\n After extract leaf node");
console.log("\n Preorder : ");
tree.preOrder(tree.root);
tree.printDoublyList();
}
}
BinaryTree.main();
/*
file : code.ts
tsc --target es6 code.ts
node code.js
*/
Output
Preorder :
10
6
2
9
3
8
7
-6
5
13
After extract leaf node
Preorder :
10
6
2
8
7
5
Doubly Linked list :
9
3
-6
13
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