Skip to main content

Flatten binary tree in order of postorder traversal in swift

Flattening tree nodes in order of postorder traversal

Swift program for Flatten binary tree in order of postorder traversal. Here mentioned other language solution.

import Foundation
/* 
  Swift 4 program for
  Flatten binary tree in order of post-order traversal
*/
// Node of Binary Tree
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	var back: TreeNode? ;
	init()
	{
		self.root = nil;
		self.back = nil;
	}
	// Recursive function
	// Display postorder view of binary tree
	func postOrder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.postOrder(node!.left);
			self.postOrder(node!.right);
			// Print node value
			print(" ",node!.data, terminator: "");
		}
	}
	// This are flattening tree nodes in postorder from
	func transform(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			// Recursive executing left and right subtree
			self.transform(node!.left);
			self.transform(node!.right);
			if (self.back == nil)
			{
				// This is first node of postorder traversal
				// Get first node of transform tree
				self.root = node;
			}
			else
			{
				// Next node
				self.back!.right = node;
				// We taking only one direction
				self.back!.left = nil;
			}
			self.back = node;
		}
	}
	// This are handling the request of
	// flatten tree nodes in post order from.
	func flattenNode()
	{
		if (self.root == nil)
		{
			// When empty tree
			return;
		}
		// Set back node
		self.back = nil;
		// Perform flatten operation
		self.transform(self.root);
		if (self.back  != nil)
		{
			// Set last node of post order
			self.back!.left = nil;
			self.back!.right = nil;
		}
		self.back = nil;
	}
	// Display flatten elements of tree
	func showElement()
	{
		if (self.root == nil)
		{
			print("\n Empty Tree");
			return;
		}
		print("\n Flatten Tree Node in Postorder : ");
		var temp: TreeNode? = self.root;
		// Iterate tree elements
		while (temp  != nil)
		{
			// Display node value
			print(" ",temp!.data, terminator: "");
			// Visit to next node
			temp = temp!.right;
		}
	}
	static func main()
	{
		// New tree
		let tree: BinaryTree = BinaryTree();
		/*
		    Construct Binary Tree
		    -----------------------
		           1
		          / \ 
		         /   \
		        6     8
		       / \   / \
		      2   3 7   5
		     /   /   \   \
		    9   4    -6   11
		*/
		// Add nodes
		tree.root = TreeNode(1);
		tree.root!.left = TreeNode(6);
		tree.root!.left!.left = TreeNode(2);
		tree.root!.right = TreeNode(8);
		tree.root!.right!.right = TreeNode(5);
		tree.root!.right!.left = TreeNode(7);
		tree.root!.right!.left!.right = TreeNode(-6);
		tree.root!.left!.right = TreeNode(3);
		tree.root!.left!.right!.left = TreeNode(4);
		tree.root!.left!.left!.left = TreeNode(9);
		tree.root!.right!.right!.right = TreeNode(11);
		// Display tree elements
		print("\n Postorder Nodes : ");
		tree.postOrder(tree.root);
		// Testing
		tree.flattenNode();
		// After transform
		tree.showElement();
	}
}
BinaryTree.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