Flatten binary tree in order of postorder traversal in swift

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