Flatten binary tree in order of post-order traversal
Here given code implementation process.
/*
C Program
Flatten binary tree in order of post-order traversal
*/
#include <stdio.h>
#include <stdlib.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
//Recursive function
//Display postorder view of binary tree
void post_order(struct Node *node)
{
if (node != NULL)
{
post_order(node->left);
post_order(node->right);
//Print node value
printf(" %d", node->data);
}
}
//This are flattening tree nodes in postorder from
void flatten_nodes(struct Node **root, struct Node *node, struct Node **back)
{
if (node != NULL)
{
//recursive executing left and right subtree
flatten_nodes(root, node->left, back);
flatten_nodes(root, node->right, back);
if ( *back == NULL)
{
//This is first node of postorder traversal
//Get first node of transform tree
*root = node;*back = node;
}
else
{
(*back)->right = node;
(*back)->left = NULL;
*back = node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
void transform(struct Node **root)
{
if ( *root == NULL)
{
return;
}
struct Node *back = NULL;
flatten_nodes(root, *root, &back);
if (back != NULL)
{
//Set last node of post order
back->left = NULL;
back->right = NULL;
}
}
//Display flatten elements of tree
void show_element(struct Node *root)
{
if (root == NULL)
{
printf("\n Empty Tree\n");
return;
}
printf("\n Flatten Tree Node in Postorder : \n");
struct Node *temp = root;
while (temp != NULL)
{
printf(" %d", temp->data);
//visit to next node
temp = temp->right;
}
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
root = get_node(1);
root->left = get_node(6);
root->left->left = get_node(2);
root->right = get_node(8);
root->right->right = get_node(5);
root->right->left = get_node(7);
root->right->left->right = get_node(-6);
root->left->right = get_node(3);
root->left->right->left = get_node(4);
root->left->left->left = get_node(9);
root->right->right->right = get_node(11);
//Display tree elements
printf("\n Postorder Nodes : \n");
post_order(root);
printf("\n");
transform( &root);
show_element(root);
return 0;
}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/*
Java Program
Flatten binary tree in order of post-order traversal
*/
//Node of Binary Tree
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
public Node root;
public Node back;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
this.back = null;
}
//Recursive function
//Display postorder view of binary tree
public void post_order(Node node)
{
if (node != null)
{
post_order(node.left);
post_order(node.right);
//Print node value
System.out.print(" " + node.data);
}
}
//This are flattening tree nodes in postorder from
public void flatten_nodes(Node node)
{
if (node != null)
{
//recursive executing left and right subtree
flatten_nodes(node.left);
flatten_nodes(node.right);
if (this.back == null)
{
//This is first node of postorder traversal
//Get first node of transform tree
this.root = node;
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
public void transform()
{
if (this.root == null)
{
// When empty tree
return;
}
// Set back node
this.back = null;
//Perform flatten operation
flatten_nodes(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
public void show_element()
{
if (this.root == null)
{
System.out.print("\n Empty Tree\n");
return;
}
System.out.print("\n Flatten Tree Node in Postorder : \n");
Node temp = this.root;
//Iterate tree elements
while (temp != null)
{
//Display node value
System.out.print(" " + temp.data);
//visit to next node
temp = temp.right;
}
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
obj.root = new Node(1);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(5);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(-6);
obj.root.left.right = new Node(3);
obj.root.left.right.left = new Node(4);
obj.root.left.left.left = new Node(9);
obj.root.right.right.right = new Node(11);
//Display tree elements
System.out.print("\n Postorder Nodes : \n");
obj.post_order(obj.root);
System.out.print("\n");
obj.transform();
//After transform
obj.show_element();;
}
}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//Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Flatten binary tree in order of post-order traversal
*/
//Node of Binary Tree
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
//Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
Node *root;
Node *back;
BinaryTree()
{
//Set initial tree root to null
this->root = NULL;
//set initial Back node is null
this->back = NULL;
}
//Recursive function
//Display postorder view of binary tree
void post_order(Node *node)
{
if (node != NULL)
{
this->post_order(node->left);
this->post_order(node->right);
//Print node value
cout << " " << node->data;
}
}
//This are flattening tree nodes in postorder from
void flatten_nodes(Node *node)
{
if (node != NULL)
{
//recursive executing left and right subtree
this->flatten_nodes(node->left);
this->flatten_nodes(node->right);
if (this->back == NULL)
{
//This is first node of postorder traversal
//Get first node of transform tree
this->root = node;
this->back = node;
}
else
{
this->back->right = node;
this->back->left = NULL;
this->back = node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
void transform()
{
if (this->root == NULL)
{
// When empty tree
return;
}
// Set back node
this->back = NULL;
//Perform flatten operation
this->flatten_nodes(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
void show_element()
{
if (this->root == NULL)
{
cout << "\n Empty Tree\n";
return;
}
cout << "\n Flatten Tree Node in Postorder : \n";
Node *temp = this->root;
//Iterate tree elements
while (temp != NULL)
{
//Display node value
cout << " " << temp->data;
//visit to next node
temp = temp->right;
}
}
};
int main()
{
//Make object of Binary Tree
BinaryTree obj = BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
obj.root = new Node(1);
obj.root->left = new Node(6);
obj.root->left->left = new Node(2);
obj.root->right = new Node(8);
obj.root->right->right = new Node(5);
obj.root->right->left = new Node(7);
obj.root->right->left->right = new Node(-6);
obj.root->left->right = new Node(3);
obj.root->left->right->left = new Node(4);
obj.root->left->left->left = new Node(9);
obj.root->right->right->right = new Node(11);
//Display tree elements
cout << "\n Postorder Nodes : \n";
obj.post_order(obj.root);
cout << "\n";
obj.transform();
//After transform
obj.show_element();;
return 0;
}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//Include namespace system
using System;
/*
C# Program
Flatten binary tree in order of post-order traversal
*/
//Node of Binary Tree
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
//Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
public Node root;
public Node back;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
//set initial Back node is null
this.back = null;
}
//Recursive function
//Display postorder view of binary tree
public void post_order(Node node)
{
if (node != null)
{
post_order(node.left);
post_order(node.right);
//Print node value
Console.Write(" " + node.data);
}
}
//This are flattening tree nodes in postorder from
public void flatten_nodes(Node node)
{
if (node != null)
{
//recursive executing left and right subtree
flatten_nodes(node.left);
flatten_nodes(node.right);
if (this.back == null)
{
//This is first node of postorder traversal
//Get first node of transform tree
this.root = node;
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
public void transform()
{
if (this.root == null)
{
// When empty tree
return;
}
// Set back node
this.back = null;
//Perform flatten operation
flatten_nodes(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
public void show_element()
{
if (this.root == null)
{
Console.Write("\n Empty Tree\n");
return;
}
Console.Write("\n Flatten Tree Node in Postorder : \n");
Node temp = this.root;
//Iterate tree elements
while (temp != null)
{
//Display node value
Console.Write(" " + temp.data);
//visit to next node
temp = temp.right;
}
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
obj.root = new Node(1);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(5);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(-6);
obj.root.left.right = new Node(3);
obj.root.left.right.left = new Node(4);
obj.root.left.left.left = new Node(9);
obj.root.right.right.right = new Node(11);
//Display tree elements
Console.Write("\n Postorder Nodes : \n");
obj.post_order(obj.root);
Console.Write("\n");
obj.transform();
//After transform
obj.show_element();;
}
}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<?php
/*
Php Program
Flatten binary tree in order of post-order traversal
*/
//Node of Binary Tree
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
//Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
public $back;
function __construct()
{
//Set initial tree root to null
$this->root = null;
//set initial Back node is null
$this->back = null;
}
//Recursive function
//Display postorder view of binary tree
public function post_order($node)
{
if ($node != null)
{
$this->post_order($node->left);
$this->post_order($node->right);
//Print node value
echo " ". $node->data;
}
}
//This are flattening tree nodes in postorder from
public function flatten_nodes($node)
{
if ($node != null)
{
//recursive executing left and right subtree
$this->flatten_nodes($node->left);
$this->flatten_nodes($node->right);
if ($this->back == null)
{
//This is first node of postorder traversal
//Get first node of transform tree
$this->root = $node;
$this->back = $node;
}
else
{
$this->back->right = $node;
$this->back->left = null;
$this->back = $node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
public function transform()
{
if ($this->root == null)
{
// When empty tree
return;
}
// Set back node
$this->back = null;
//Perform flatten operation
$this->flatten_nodes($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
public function show_element()
{
if ($this->root == null)
{
echo "\n Empty Tree\n";
return;
}
echo "\n Flatten Tree Node in Postorder : \n";
$temp = $this->root;
//Iterate tree elements
while ($temp != null)
{
//Display node value
echo " ". $temp->data;
//visit to next node
$temp = $temp->right;
}
}
}
function main()
{
//Make object of Binary Tree
$obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
$obj->root = new Node(1);
$obj->root->left = new Node(6);
$obj->root->left->left = new Node(2);
$obj->root->right = new Node(8);
$obj->root->right->right = new Node(5);
$obj->root->right->left = new Node(7);
$obj->root->right->left->right = new Node(-6);
$obj->root->left->right = new Node(3);
$obj->root->left->right->left = new Node(4);
$obj->root->left->left->left = new Node(9);
$obj->root->right->right->right = new Node(11);
//Display tree elements
echo "\n Postorder Nodes : \n";
$obj->post_order($obj->root);
echo "\n";
$obj->transform();
//After transform
$obj->show_element();;
}
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/*
Node Js Program
Flatten binary tree in order of post-order traversal
*/
//Node of Binary Tree
class Node
{
constructor(data)
{
//Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
//Set initial tree root to null
this.root = null;
//set initial Back node is null
this.back = null;
}
//Recursive function
//Display postorder view of binary tree
post_order(node)
{
if (node != null)
{
this.post_order(node.left);
this.post_order(node.right);
//Print node value
process.stdout.write(" " + node.data);
}
}
//This are flattening tree nodes in postorder from
flatten_nodes(node)
{
if (node != null)
{
//recursive executing left and right subtree
this.flatten_nodes(node.left);
this.flatten_nodes(node.right);
if (this.back == null)
{
//This is first node of postorder traversal
//Get first node of transform tree
this.root = node;
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
transform()
{
if (this.root == null)
{
// When empty tree
return;
}
// Set back node
this.back = null;
//Perform flatten operation
this.flatten_nodes(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
show_element()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree\n");
return;
}
process.stdout.write("\n Flatten Tree Node in Postorder : \n");
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()
{
//Make object of Binary Tree
var obj = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
obj.root = new Node(1);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(5);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(-6);
obj.root.left.right = new Node(3);
obj.root.left.right.left = new Node(4);
obj.root.left.left.left = new Node(9);
obj.root.right.right.right = new Node(11);
//Display tree elements
process.stdout.write("\n Postorder Nodes : \n");
obj.post_order(obj.root);
process.stdout.write("\n");
obj.transform();
//After transform
obj.show_element();;
}
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# Python 3 Program
# Flatten binary tree in order of post-order traversal
# Node of Binary Tree
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
# Set initial tree root to null
self.root = None
# set initial Back node is null
self.back = None
# Recursive function
# Display postorder view of binary tree
def post_order(self, node) :
if (node != None) :
self.post_order(node.left)
self.post_order(node.right)
# Print node value
print(" ", node.data, end = "")
# This are flattening tree nodes in postorder from
def flatten_nodes(self, node) :
if (node != None) :
# recursive executing left and right subtree
self.flatten_nodes(node.left)
self.flatten_nodes(node.right)
if (self.back == None) :
# This is first node of postorder traversal
# Get first node of transform tree
self.root = node
self.back = node
else :
self.back.right = node
self.back.left = None
self.back = node
# This are handling the request of flatten tree nodes in post order from
def transform(self) :
if (self.root == None) :
# When empty tree
return
# Set back node
self.back = None
# Perform flatten operation
self.flatten_nodes(self.root)
if (self.back != None) :
# Set last node of post order
self.back.left = None
self.back.right = None
self.back = None
# Display flatten elements of tree
def show_element(self) :
if (self.root == None) :
print("\n Empty Tree\n", end = "")
return
print("\n Flatten Tree Node in Postorder : \n", end = "")
temp = self.root
# Iterate tree elements
while (temp != None) :
# Display node value
print(" ", temp.data, end = "")
# visit to next node
temp = temp.right
def main() :
# Make object of Binary Tree
obj = BinaryTree()
#
# Construct Binary Tree
# -----------------------
# 1
# / \
# 6 8
# / \ / \
# 2 3 7 5
# / / \ \
# 9 4 -6 11
#
#
# Add nodes
obj.root = Node(1)
obj.root.left = Node(6)
obj.root.left.left = Node(2)
obj.root.right = Node(8)
obj.root.right.right = Node(5)
obj.root.right.left = Node(7)
obj.root.right.left.right = Node(-6)
obj.root.left.right = Node(3)
obj.root.left.right.left = Node(4)
obj.root.left.left.left = Node(9)
obj.root.right.right.right = Node(11)
# Display tree elements
print("\n Postorder Nodes : \n", end = "")
obj.post_order(obj.root)
print("\n", end = "")
obj.transform()
# After transform
obj.show_element()
if __name__ == "__main__": 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#
# Ruby Program
# Flatten binary tree in order of post-order traversal
# Node of Binary Tree
class Node
# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root, :back
attr_accessor :root, :back
def initialize()
# Set initial tree root to null
self.root = nil
# set initial Back node is null
self.back = nil
end
# Recursive function
# Display postorder view of binary tree
def post_order(node)
if (node != nil)
self.post_order(node.left)
self.post_order(node.right)
# Print node value
print(" ", node.data)
end
end
# This are flattening tree nodes in postorder from
def flatten_nodes(node)
if (node != nil)
# recursive executing left and right subtree
self.flatten_nodes(node.left)
self.flatten_nodes(node.right)
if (self.back == nil)
# This is first node of postorder traversal
# Get first node of transform tree
self.root = node
self.back = node
else
self.back.right = node
self.back.left = nil
self.back = node
end
end
end
# This are handling the request of flatten tree nodes in post order from
def transform()
if (self.root == nil)
# When empty tree
return
end
# Set back node
self.back = nil
# Perform flatten operation
self.flatten_nodes(self.root)
if (self.back != nil)
# Set last node of post order
self.back.left = nil
self.back.right = nil
end
self.back = nil
end
# Display flatten elements of tree
def show_element()
if (self.root == nil)
print("\n Empty Tree\n")
return
end
print("\n Flatten Tree Node in Postorder : \n")
temp = self.root
# Iterate tree elements
while (temp != nil)
# Display node value
print(" ", temp.data)
# visit to next node
temp = temp.right
end
end
end
def main()
# Make object of Binary Tree
obj = BinaryTree.new()
#
# Construct Binary Tree
# -----------------------
# 1
# / \
# 6 8
# / \ / \
# 2 3 7 5
# / / \ \
# 9 4 -6 11
#
#
# Add nodes
obj.root = Node.new(1)
obj.root.left = Node.new(6)
obj.root.left.left = Node.new(2)
obj.root.right = Node.new(8)
obj.root.right.right = Node.new(5)
obj.root.right.left = Node.new(7)
obj.root.right.left.right = Node.new(-6)
obj.root.left.right = Node.new(3)
obj.root.left.right.left = Node.new(4)
obj.root.left.left.left = Node.new(9)
obj.root.right.right.right = Node.new(11)
# Display tree elements
print("\n Postorder Nodes : \n")
obj.post_order(obj.root)
print("\n")
obj.transform()
# After transform
obj.show_element()
end
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/*
Scala Program
Flatten binary tree in order of post-order traversal
*/
//Node of Binary Tree
class Node(var data: Int,
var left: Node,
var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: Node,
var back: Node)
{
def this()
{
this(null, null);
}
//Recursive function
//Display postorder view of binary tree
def post_order(node: Node): Unit = {
if (node != null)
{
post_order(node.left);
post_order(node.right);
//Print node value
print(" " + node.data);
}
}
//This are flattening tree nodes in postorder from
def flatten_nodes(node: Node): Unit = {
if (node != null)
{
//recursive executing left and right subtree
flatten_nodes(node.left);
flatten_nodes(node.right);
if (this.back == null)
{
//This is first node of postorder traversal
//Get first node of transform tree
this.root = node;
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
def transform(): Unit = {
if (this.root == null)
{
// When empty tree
return;
}
// Set back node
this.back = null;
//Perform flatten operation
flatten_nodes(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
def show_element(): Unit = {
if (this.root == null)
{
print("\n Empty Tree\n");
return;
}
print("\n Flatten Tree Node in Postorder : \n");
var temp: Node = this.root;
//Iterate tree elements
while (temp != null)
{
//Display node value
print(" " + temp.data);
//visit to next node
temp = temp.right;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Binary Tree
var obj: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
obj.root = new Node(1);
obj.root.left = new Node(6);
obj.root.left.left = new Node(2);
obj.root.right = new Node(8);
obj.root.right.right = new Node(5);
obj.root.right.left = new Node(7);
obj.root.right.left.right = new Node(-6);
obj.root.left.right = new Node(3);
obj.root.left.right.left = new Node(4);
obj.root.left.left.left = new Node(9);
obj.root.right.right.right = new Node(11);
//Display tree elements
print("\n Postorder Nodes : \n");
obj.post_order(obj.root);
print("\n");
obj.transform();
//After transform
obj.show_element();
}
}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/*
Swift 4 Program
Flatten binary tree in order of post-order traversal
*/
//Node of Binary Tree
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
//Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: Node? ;
var back: Node? ;
init()
{
//Set initial tree root to null
self.root = nil;
//set initial Back node is null
self.back = nil;
}
//Recursive function
//Display postorder view of binary tree
func post_order(_ node: Node? )
{
if (node != nil)
{
self.post_order(node!.left);
self.post_order(node!.right);
//Print node value
print(" ", node!.data, terminator: "");
}
}
//This are flattening tree nodes in postorder from
func flatten_nodes(_ node: Node? )
{
if (node != nil)
{
//recursive executing left and right subtree
self.flatten_nodes(node!.left);
self.flatten_nodes(node!.right);
if (self.back == nil)
{
//This is first node of postorder traversal
//Get first node of transform tree
self.root = node;
self.back = node;
}
else
{
self.back!.right = node;
self.back!.left = nil;
self.back = node;
}
}
}
//This are handling the request of flatten tree nodes in post order from
func transform()
{
if (self.root == nil)
{
// When empty tree
return;
}
// Set back node
self.back = nil;
//Perform flatten operation
self.flatten_nodes(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 show_element()
{
if (self.root == nil)
{
print("\n Empty Tree\n", terminator: "");
return;
}
print("\n Flatten Tree Node in Postorder : \n", terminator: "");
var temp: Node? = self.root;
//Iterate tree elements
while (temp != nil)
{
//Display node value
print(" ", temp!.data, terminator: "");
//visit to next node
temp = temp!.right;
}
}
}
func main()
{
//Make object of Binary Tree
let obj: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------
1
/ \
6 8
/ \ / \
2 3 7 5
/ / \ \
9 4 -6 11
*/
//Add nodes
obj.root = Node(1);
obj.root!.left = Node(6);
obj.root!.left!.left = Node(2);
obj.root!.right = Node(8);
obj.root!.right!.right = Node(5);
obj.root!.right!.left = Node(7);
obj.root!.right!.left!.right = Node(-6);
obj.root!.left!.right = Node(3);
obj.root!.left!.right!.left = Node(4);
obj.root!.left!.left!.left = Node(9);
obj.root!.right!.right!.right = Node(11);
//Display tree elements
print("\n Postorder Nodes : \n", terminator: "");
obj.post_order(obj.root);
print("\n", terminator: "");
obj.transform();
//After transform
obj.show_element();
}
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