Skip to main content

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




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