Skip to main content

Flatten binary tree in order of postorder traversal in node js

Flattening tree nodes in order of postorder traversal

Js program for Flatten binary tree in order of postorder traversal. Here more solutions.

/* 
  Node JS program for
  Flatten binary tree in order of post-order traversal
*/
// Node of Binary Tree
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
		this.back = null;
	}
	// Recursive function
	// Display postorder view of binary tree
	postOrder(node)
	{
		if (node != null)
		{
			this.postOrder(node.left);
			this.postOrder(node.right);
			// Print node value
			process.stdout.write("  " + node.data);
		}
	}
	// This are flattening tree nodes in postorder from
	transform(node)
	{
		if (node != null)
		{
			// Recursive executing left and right subtree
			this.transform(node.left);
			this.transform(node.right);
			if (this.back == null)
			{
				// This is first node of postorder traversal
				// Get first node of transform tree
				this.root = node;
			}
			else
			{
				// Next node
				this.back.right = node;
				// We taking only one direction
				this.back.left = null;
			}
			this.back = node;
		}
	}
	// This are handling the request of
	// flatten tree nodes in post order from.
	flattenNode()
	{
		if (this.root == null)
		{
			// When empty tree
			return;
		}
		// Set back node
		this.back = null;
		// Perform flatten operation
		this.transform(this.root);
		if (this.back != null)
		{
			// Set last node of post order
			this.back.left = null;
			this.back.right = null;
		}
		this.back = null;
	}
	// Display flatten elements of tree
	showElement()
	{
		if (this.root == null)
		{
			console.log("\n Empty Tree");
			return;
		}
		console.log("\n Flatten Tree Node in Postorder : ");
		var temp = this.root;
		// Iterate tree elements
		while (temp != null)
		{
			// Display node value
			process.stdout.write("  " + temp.data);
			// Visit to next node
			temp = temp.right;
		}
	}
}

function main()
{
	// New tree
	var tree = new BinaryTree();
	/*
	    Construct Binary Tree
	    -----------------------
	           1
	          / \ 
	         /   \
	        6     8
	       / \   / \
	      2   3 7   5
	     /   /   \   \
	    9   4    -6   11
	*/
	// Add nodes
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(6);
	tree.root.left.left = new TreeNode(2);
	tree.root.right = new TreeNode(8);
	tree.root.right.right = new TreeNode(5);
	tree.root.right.left = new TreeNode(7);
	tree.root.right.left.right = new TreeNode(-6);
	tree.root.left.right = new TreeNode(3);
	tree.root.left.right.left = new TreeNode(4);
	tree.root.left.left.left = new TreeNode(9);
	tree.root.right.right.right = new TreeNode(11);
	// Display tree elements
	console.log("\n Postorder Nodes : ");
	tree.postOrder(tree.root);
	// Testing
	tree.flattenNode();
	// After transform
	tree.showElement();
}
// Start program execution
main();

Output

 Postorder Nodes :
  9  2  4  3  6  -6  7  11  5  8  1
 Flatten Tree Node in Postorder :
  9  2  4  3  6  -6  7  11  5  8  1




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