Flatten a binary tree into linked list
Here given code implementation process.
/*
C Program
Flatten a binary tree into linked list
*/
#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 preorder view of binary tree
void preorder(struct Node *node)
{
if (node)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
//This are flattening tree nodes in inorder from
void flatten_nodes(struct Node *node, struct Node **back)
{
if (node == NULL)
{
return;
}
//Get right subtree of node
struct Node *right_side = node->right;
if ( *back == NULL)
{
//When first node of tree
*back = node;
}
else
{
//connect previous node to current node
(*back)->right = node;
(*back)->left = NULL;
*back = node;
}
flatten_nodes(node->left, back);
flatten_nodes(right_side, back);
}
//This are handling the request of flatten tree nodes in pre order from
void transform(struct Node *root)
{
if (root == NULL)
{
return;
}
struct Node *back = NULL;
flatten_nodes(root, &back);
if (back != NULL)
{
//Set last node of pre 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 is :");
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 Preorder Tree Nodes : ");
preorder(root);
printf("\n");
transform(root);
//After transform
show_element(root);
return 0;
}
Output
Preorder Tree Nodes : 1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node is : 1 6 2 9 3 4 8 7 -6 5 11
/*
Java Program
Flatten a binary tree into linked list
*/
//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 preorder view of binary tree
public void preorder(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
//This are flattening tree nodes in preorder from
public void flatten_nodes(Node node)
{
if (node != null)
{
//Get right subtree of node
Node right_side = node.right;
if (this.back == null)
{
//This is first node of preorder traversal
//Get first node of transform tree
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
//recursive executing left and right subtree
flatten_nodes(node.left);
flatten_nodes(right_side);
}
}
//This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n");
obj.preorder(obj.root);
//Perform transformation
obj.transform();
//After transform
obj.show_element();;
}
}
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
//Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Flatten a binary tree into linked list
*/
//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;
this->back = NULL;
}
//Recursive function
//Display preorder view of binary tree
void preorder(Node *node)
{
if (node != NULL)
{
//Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
//This are flattening tree nodes in preorder from
void flatten_nodes(Node *node)
{
if (node != NULL)
{
//Get right subtree of node
Node *right_side = node->right;
if (this->back == NULL)
{
//This is first node of preorder traversal
//Get first node of transform tree
this->back = node;
}
else
{
this->back->right = node;
this->back->left = NULL;
this->back = node;
}
//recursive executing left and right subtree
this->flatten_nodes(node->left);
this->flatten_nodes(right_side);
}
}
//This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n";
obj.preorder(obj.root);
//Perform transformation
obj.transform();
//After transform
obj.show_element();;
return 0;
}
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
//Include namespace system
using System;
/*
C# Program
Flatten a binary tree into linked list
*/
//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 preorder view of binary tree
public void preorder(Node node)
{
if (node != null)
{
//Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
//This are flattening tree nodes in preorder from
public void flatten_nodes(Node node)
{
if (node != null)
{
//Get right subtree of node
Node right_side = node.right;
if (this.back == null)
{
//This is first node of preorder traversal
//Get first node of transform tree
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
//recursive executing left and right subtree
flatten_nodes(node.left);
flatten_nodes(right_side);
}
}
//This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n");
obj.preorder(obj.root);
//Perform transformation
obj.transform();
//After transform
obj.show_element();;
}
}
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
<?php
/*
Php Program
Flatten a binary tree into linked list
*/
//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;
$this->back = null;
}
//Recursive function
//Display preorder view of binary tree
public function preorder($node)
{
if ($node != null)
{
//Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
//This are flattening tree nodes in preorder from
public function flatten_nodes($node)
{
if ($node != null)
{
//Get right subtree of node
$right_side = $node->right;
if ($this->back == null)
{
//This is first node of preorder traversal
//Get first node of transform tree
$this->back = $node;
}
else
{
$this->back->right = $node;
$this->back->left = null;
$this->back = $node;
}
//recursive executing left and right subtree
$this->flatten_nodes($node->left);
$this->flatten_nodes($right_side);
}
}
//This are handling the request of flatten tree nodes in perorde 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 perorde
$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 preorder : \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 Preorder Tree Nodes : \n";
$obj->preorder($obj->root);
//Perform transformation
$obj->transform();
//After transform
$obj->show_element();;
}
main();
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
/*
Node Js Program
Flatten a binary tree into linked list
*/
//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;
this.back = null;
}
//Recursive function
//Display preorder view of binary tree
preorder(node)
{
if (node != null)
{
//Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
//This are flattening tree nodes in preorder from
flatten_nodes(node)
{
if (node != null)
{
//Get right subtree of node
var right_side = node.right;
if (this.back == null)
{
//This is first node of preorder traversal
//Get first node of transform tree
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
//recursive executing left and right subtree
this.flatten_nodes(node.left);
this.flatten_nodes(right_side);
}
}
//This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n");
obj.preorder(obj.root);
//Perform transformation
obj.transform();
//After transform
obj.show_element();;
}
main();
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
# Python 3 Program
# Flatten a binary tree into linked list
# 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
self.back = None
# Recursive function
# Display preorder view of binary tree
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
# This are flattening tree nodes in preorder from
def flatten_nodes(self, node) :
if (node != None) :
# Get right subtree of node
right_side = node.right
if (self.back == None) :
# This is first node of preorder traversal
# Get first node of transform tree
self.back = node
else :
self.back.right = node
self.back.left = None
self.back = node
# recursive executing left and right subtree
self.flatten_nodes(node.left)
self.flatten_nodes(right_side)
# This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n", end = "")
obj.preorder(obj.root)
# Perform transformation
obj.transform()
# After transform
obj.show_element()
if __name__ == "__main__": main()
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
# Ruby Program
# Flatten a binary tree into linked list
# 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
self.back = nil
end
# Recursive function
# Display preorder view of binary tree
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
# This are flattening tree nodes in preorder from
def flatten_nodes(node)
if (node != nil)
# Get right subtree of node
right_side = node.right
if (self.back == nil)
# This is first node of preorder traversal
# Get first node of transform tree
self.back = node
else
self.back.right = node
self.back.left = nil
self.back = node
end
# recursive executing left and right subtree
self.flatten_nodes(node.left)
self.flatten_nodes(right_side)
end
end
# This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n")
obj.preorder(obj.root)
# Perform transformation
obj.transform()
# After transform
obj.show_element()
end
main()
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
/*
Scala Program
Flatten a binary tree into linked list
*/
//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 preorder view of binary tree
def preorder(node: Node): Unit = {
if (node != null)
{
//Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
//This are flattening tree nodes in preorder from
def flatten_nodes(node: Node): Unit = {
if (node != null)
{
//Get right subtree of node
var right_side: Node = node.right;
if (this.back == null)
{
//This is first node of preorder traversal
//Get first node of transform tree
this.back = node;
}
else
{
this.back.right = node;
this.back.left = null;
this.back = node;
}
//recursive executing left and right subtree
flatten_nodes(node.left);
flatten_nodes(right_side);
}
}
//This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n");
obj.preorder(obj.root);
//Perform transformation
obj.transform();
//After transform
obj.show_element();
}
}
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
/*
Swift 4 Program
Flatten a binary tree into linked list
*/
//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;
self.back = nil;
}
//Recursive function
//Display preorder view of binary tree
func preorder(_ node: Node? )
{
if (node != nil)
{
//Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
//This are flattening tree nodes in preorder from
func flatten_nodes(_ node: Node? )
{
if (node != nil)
{
//Get right subtree of node
let right_side: Node? = node!.right;
if (self.back == nil)
{
//This is first node of preorder traversal
//Get first node of transform tree
self.back = node;
}
else
{
self.back!.right = node;
self.back!.left = nil;
self.back = node;
}
//recursive executing left and right subtree
self.flatten_nodes(node!.left);
self.flatten_nodes(right_side);
}
}
//This are handling the request of flatten tree nodes in perorde 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 perorde
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 preorder : \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 Preorder Tree Nodes : \n", terminator: "");
obj.preorder(obj.root);
//Perform transformation
obj.transform();
//After transform
obj.show_element();
}
main();
Output
Preorder Tree Nodes :
1 6 2 9 3 4 8 7 -6 5 11
Flatten Tree Node in preorder :
1 6 2 9 3 4 8 7 -6 5 11
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