Binary tree down-right conversion
Here given code implementation process.
/*
C Program
+ Convert left-right representation of a binary tree to down-right
*/
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Tree node
struct Node
{
int data;
struct Node*left,*right;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node* newNode(int data)
{
//create dynamic memory to new binary tree 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; //Initially node left-pointer is NULL
new_node->right=NULL;//Initially node right-pointer is NULL
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;
}
void convert(struct Node*root)
{
if(root==NULL) return ;
convert(root->left);
convert(root->right);
if(root->left==NULL)
{
//change left child
root->left=root->right;
}
else
{
root->left->right=root->right;
}
root->right=NULL;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%3d",root->data);
inorder(root->right);
}
}
//Display tree element preorder form
void preorder(struct Node*node){
if(node){
//Print node value
printf(" %d",node->data);
preorder(node->left);
preorder(node->right);
}
}
//Display tree element postorder form
void postorder(struct Node*node){
if(node){
postorder(node->left);
postorder(node->right);
//Print node value
printf(" %d",node->data);
}
}
int main(){
struct Node*root=NULL;
/* Make A Binary Tree
-----------------------
1
/ \
2 4
/ / \
3 6 5
\ / \ \
7 9 8 0
*/
//add nodes
root =newNode(1);
root->left =newNode(2);
root->left->left =newNode(3);
root->left->left->right =newNode(7);
root->right =newNode(4);
root->right->right =newNode(5);
root->right->right->right =newNode(0);
root->right->left =newNode(6);
root->right->left->left =newNode(9);
root->right->left->right =newNode(8);
printf("Before");
printf("\n Inorder : \n");
inorder(root);
printf("\n Preorder : \n");
preorder(root);
printf("\n Postorder : \n");
postorder(root);
/*
1
│
2――――4
│ │
3 6―――――――5
│ │ │
7 9―――8 0
*/
convert(root);
printf("\nAfter");
printf("\n Inorder : \n");
inorder(root);
printf("\n Preorder : \n");
preorder(root);
printf("\n Postorder : \n");
postorder(root);
return 0;
}
Output
Before
Inorder :
3 7 2 1 9 6 8 4 5 0
Preorder :
1 2 3 7 4 6 9 8 5 0
Postorder :
7 3 2 9 8 6 0 5 4 1
After
Inorder :
7 3 2 9 8 6 0 5 4 1
Preorder :
1 2 3 7 4 6 9 8 5 0
Postorder :
7 3 8 9 0 5 6 4 2 1/*
C++ Program
Convert left-right representation of a binary tree to down-right
*/
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int value) {
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree {
public:
Node *root;
BinaryTree() {
this->root = NULL;
}
void in_order(Node *node) {
if (node != NULL) {
this->in_order(node->left);
cout << " " << node->data;
this->in_order(node->right);
}
}
void pre_order(Node *node) {
if (node != NULL) {
cout << " " << node->data;
this->pre_order(node->left);
this->pre_order(node->right);
}
}
void post_order(Node *node) {
if (node != NULL) {
this->post_order(node->left);
this->post_order(node->right);
cout << " " << node->data;
}
}
void convert(Node *head) {
if (head == NULL) {
return;
}
this->convert(head->left);
this->convert(head->right);
if (head->left == NULL) {
head->left = head->right;
} else {
head->left->right = head->right;
}
head->right = NULL;
}
};
int main() {
BinaryTree obj;
/* Make A Binary Tree
---------------------
1
/ \
2 4
/ / \
3 6 5
\ / \ \
7 9 8 0
*/
obj.root = new Node(1);
obj.root->left = new Node(2);
obj.root->left->left = new Node(3);
obj.root->left->left->right = new Node(7);
obj.root->right = new Node(4);
obj.root->right->right = new Node(5);
obj.root->right->right->right = new Node(0);
obj.root->right->left = new Node(6);
obj.root->right->left->left = new Node(9);
obj.root->right->left->right = new Node(8);
cout << "\n Before convert";
cout << "\nIn-order Data : ";
obj.in_order(obj.root);
cout << "\nPre-order Data : ";
obj.pre_order(obj.root);
cout << "\nPost-order Data : ";
obj.post_order(obj.root);
obj.convert(obj.root);
cout << "\n After convert";
cout << "\nIn-order Data : ";
obj.in_order(obj.root);
cout << "\nPre-order Data : ";
obj.pre_order(obj.root);
cout << "\nPost-order Data : ";
obj.post_order(obj.root);
return 0;
}
Output
Before convert
In-order Data : 3 7 2 1 9 6 8 4 5 0
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 2 9 8 6 0 5 4 1
After convert
In-order Data : 7 3 2 9 8 6 0 5 4 1
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 8 9 0 5 6 4 2 1/*
Java Program
Convert left-right representation of a binary tree to down-right
*/
//Class of Binary Tree node
class Node {
public int data;
public Node left, right;
//Make a tree node
public Node(int value) {
//Assign field values
data = value;
left = null;
right = null;
}
}
public class BinaryTree {
public Node root;
public BinaryTree() {
//Set initial initial values
root = null;
}
//Display tree element inorder form
public void in_order(Node node) {
if (node != null) {
in_order(node.left);
//Print node value
System.out.print(" " + node.data);
in_order(node.right);
}
}
//Display tree element preorder form
public void pre_order(Node node) {
if (node != null) {
//Print node value
System.out.print(" " + node.data);
pre_order(node.left);
pre_order(node.right);
}
}
//Display tree element preorder form
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);
}
}
public void convert(Node head) {
if (head == null) {
return;
}
convert(head.left);
convert(head.right);
if (head.left == null) {
//change left child
head.left = head.right;
} else {
head.left.right = head.right;
}
head.right = null;
}
public static void main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 4
/ / \
3 6 5
\ / \ \
7 9 8 0
*/
//add nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.left.left = new Node(3);
obj.root.left.left.right = new Node(7);
obj.root.right = new Node(4);
obj.root.right.right = new Node(5);
obj.root.right.right.right = new Node(0);
obj.root.right.left = new Node(6);
obj.root.right.left.left = new Node(9);
obj.root.right.left.right = new Node(8);
System.out.print("\n Before convert");
System.out.print("\nIn-order Data : ");
obj.in_order(obj.root);
System.out.print("\nPre-order Data : ");
obj.pre_order(obj.root);
System.out.print("\nPost-order Data : ");
obj.post_order(obj.root);
/*
1
│
2――――4
│ │
3 6―――――――5
│ │ │
7 9―――8 0
*/
obj.convert(obj.root);
System.out.print("\n After convert");
System.out.print("\nIn-order Data : ");
obj.in_order(obj.root);
System.out.print("\nPre-order Data : ");
obj.pre_order(obj.root);
System.out.print("\nPost-order Data : ");
obj.post_order(obj.root);
}
}
Output
Before convert
In-order Data : 3 7 2 1 9 6 8 4 5 0
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 2 9 8 6 0 5 4 1
After convert
In-order Data : 7 3 2 9 8 6 0 5 4 1
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 8 9 0 5 6 4 2 1/*
C# Program
Convert left-right representation of a binary tree to down-right
*/
using System;
//Class of Binary Tree node
public class Node {
public int data;
public Node left, right;
//Make a tree node
public Node(int value) {
//Assign field values
data = value;
left = null;
right = null;
}
}
public class BinaryTree {
public Node root;
public BinaryTree() {
//Set initial initial values
root = null;
}
//Display tree element inorder form
public void in_order(Node node) {
if (node != null) {
in_order(node.left);
//Print node value
Console.Write(" " + node.data);
in_order(node.right);
}
}
//Display tree element preorder form
public void pre_order(Node node) {
if (node != null) {
//Print node value
Console.Write(" " + node.data);
pre_order(node.left);
pre_order(node.right);
}
}
//Display tree element preorder form
public void post_order(Node node) {
if (node != null) {
post_order(node.left);
post_order(node.right);
//Print node value
Console.Write(" " + node.data);
}
}
public void convert(Node head) {
if (head == null) {
return;
}
convert(head.left);
convert(head.right);
if (head.left == null) {
//change left child
head.left = head.right;
} else {
head.left.right = head.right;
}
head.right = null;
}
public static void Main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 4
/ / \
3 6 5
\ / \ \
7 9 8 0
*/
//add nodes
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.left.left = new Node(3);
obj.root.left.left.right = new Node(7);
obj.root.right = new Node(4);
obj.root.right.right = new Node(5);
obj.root.right.right.right = new Node(0);
obj.root.right.left = new Node(6);
obj.root.right.left.left = new Node(9);
obj.root.right.left.right = new Node(8);
Console.Write("\n Before convert");
Console.Write("\nIn-order Data : ");
obj.in_order(obj.root);
Console.Write("\nPre-order Data : ");
obj.pre_order(obj.root);
Console.Write("\nPost-order Data : ");
obj.post_order(obj.root);
/*
1
│
2――――4
│ │
3 6―――――――5
│ │ │
7 9―――8 0
*/
obj.convert(obj.root);
Console.Write("\n After convert");
Console.Write("\nIn-order Data : ");
obj.in_order(obj.root);
Console.Write("\nPre-order Data : ");
obj.pre_order(obj.root);
Console.Write("\nPost-order Data : ");
obj.post_order(obj.root);
}
}
Output
Before convert
In-order Data : 3 7 2 1 9 6 8 4 5 0
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 2 9 8 6 0 5 4 1
After convert
In-order Data : 7 3 2 9 8 6 0 5 4 1
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 8 9 0 5 6 4 2 1# Python Program
# Convert left-right representation of a binary tree to down-right
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def in_order(self, node) :
if (node != None) :
self.in_order(node.left)
print(node.data,end=" ")
self.in_order(node.right)
def pre_order(self, node) :
if (node != None) :
print(node.data,end=" ")
self.pre_order(node.left)
self.pre_order(node.right)
def post_order(self, node) :
if (node != None) :
self.post_order(node.left)
self.post_order(node.right)
print(node.data,end=" ")
def convert(self, head) :
if (head == None) :
return
self.convert(head.left)
self.convert(head.right)
if (head.left == None) :
head.left = head.right
else :
head.left.right = head.right
head.right = None
def main() :
obj = BinaryTree()
# Make A Binary Tree
# 1
# / \
# 2 4
# / / \
# 3 6 5
# \ / \ \
# 7 9 8 0
#
obj.root = Node(1)
obj.root.left = Node(2)
obj.root.left.left = Node(3)
obj.root.left.left.right = Node(7)
obj.root.right = Node(4)
obj.root.right.right = Node(5)
obj.root.right.right.right = Node(0)
obj.root.right.left = Node(6)
obj.root.right.left.left = Node(9)
obj.root.right.left.right = Node(8)
print("\n Before convert")
print("In-order Data : ")
obj.in_order(obj.root)
print("\nPre-order Data : ")
obj.pre_order(obj.root)
print("\nPost-order Data : ")
obj.post_order(obj.root)
obj.convert(obj.root)
print("\n After convert")
print("In-order Data : ")
obj.in_order(obj.root)
print("\nPre-order Data : ")
obj.pre_order(obj.root)
print("\nPost-order Data : ")
obj.post_order(obj.root)
if __name__ == "__main__":
main()
Output
Before convert
In-order Data :
3 7 2 1 9 6 8 4 5 0
Pre-order Data :
1 2 3 7 4 6 9 8 5 0
Post-order Data :
7 3 2 9 8 6 0 5 4 1
After convert
In-order Data :
7 3 2 9 8 6 0 5 4 1
Pre-order Data :
1 2 3 7 4 6 9 8 5 0
Post-order Data :
7 3 8 9 0 5 6 4 2 1# Ruby Program
# Convert left-right representation of a binary tree to down-right
class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end
class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
@root = nil
end
def in_order(node)
if (node != nil)
self.in_order(node.left)
print(" ", node.data)
self.in_order(node.right)
end
end
def pre_order(node)
if (node != nil)
print(" ", node.data)
self.pre_order(node.left)
self.pre_order(node.right)
end
end
def post_order(node)
if (node != nil)
self.post_order(node.left)
self.post_order(node.right)
print(" ", node.data)
end
end
def convert(head)
if (head == nil)
return
end
self.convert(head.left)
self.convert(head.right)
if (head.left == nil)
head.left = head.right
else
head.left.right = head.right
end
head.right = nil
end
end
def main()
obj = BinaryTree.new()
# Make A Binary Tree
# 1
# / \
# 2 4
# / / \
# 3 6 5
# \ / \ \
# 7 9 8 0
#
obj.root = Node.new(1)
obj.root.left = Node.new(2)
obj.root.left.left = Node.new(3)
obj.root.left.left.right = Node.new(7)
obj.root.right = Node.new(4)
obj.root.right.right = Node.new(5)
obj.root.right.right.right = Node.new(0)
obj.root.right.left = Node.new(6)
obj.root.right.left.left = Node.new(9)
obj.root.right.left.right = Node.new(8)
print("\n Before convert")
print("\nIn-order Data :")
obj.in_order(obj.root)
print("\nPre-order Data :")
obj.pre_order(obj.root)
print("\nPost-order Data :")
obj.post_order(obj.root)
obj.convert(obj.root)
print("\n After convert")
print("\nIn-order Data :")
obj.in_order(obj.root)
print("\nPre-order Data :")
obj.pre_order(obj.root)
print("\nPost-order Data :")
obj.post_order(obj.root)
end
main()
Output
Before convert
In-order Data : 3 7 2 1 9 6 8 4 5 0
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 2 9 8 6 0 5 4 1
After convert
In-order Data : 7 3 2 9 8 6 0 5 4 1
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 8 9 0 5 6 4 2 1<?php
/*
Php Program
Convert left-right representation of a binary tree to down-right
*/
class Node {
public $data;
public $left;
public $right;
function __construct($value) {
$this->data = $value;
$this->left = null;
$this->right = null;
}
}
class BinaryTree {
public $root;
function __construct() {
$this->root = null;
}
public function in_order($node) {
if ($node != null) {
$this->in_order($node->left);
echo(" ". $node->data);
$this->in_order($node->right);
}
}
public function pre_order($node) {
if ($node != null) {
echo(" ". $node->data);
$this->pre_order($node->left);
$this->pre_order($node->right);
}
}
public function post_order($node) {
if ($node != null) {
$this->post_order($node->left);
$this->post_order($node->right);
echo(" ". $node->data);
}
}
public function convert($head) {
if ($head == null) {
return;
}
$this->convert($head->left);
$this->convert($head->right);
if ($head->left == null) {
$head->left = $head->right;
} else {
$head->left->right = $head->right;
}
$head->right = null;
}
}
function main() {
$obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 4
/ / \
3 6 5
\ / \ \
7 9 8 0
*/
$obj->root = new Node(1);
$obj->root->left = new Node(2);
$obj->root->left->left = new Node(3);
$obj->root->left->left->right = new Node(7);
$obj->root->right = new Node(4);
$obj->root->right->right = new Node(5);
$obj->root->right->right->right = new Node(0);
$obj->root->right->left = new Node(6);
$obj->root->right->left->left = new Node(9);
$obj->root->right->left->right = new Node(8);
echo("\n Before convert");
echo("\nIn-order Data : ");
$obj->in_order($obj->root);
echo("\nPre-order Data : ");
$obj->pre_order($obj->root);
echo("\nPost-order Data : ");
$obj->post_order($obj->root);
$obj->convert($obj->root);
echo("\n After convert");
echo("\nIn-order Data : ");
$obj->in_order($obj->root);
echo("\nPre-order Data : ");
$obj->pre_order($obj->root);
echo("\nPost-order Data : ");
$obj->post_order($obj->root);
}
main();
Output
Before convert
In-order Data : 3 7 2 1 9 6 8 4 5 0
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 2 9 8 6 0 5 4 1
After convert
In-order Data : 7 3 2 9 8 6 0 5 4 1
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 8 9 0 5 6 4 2 1/*
Node JS Program
Convert left-right representation of a binary tree to down-right
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
in_order(node) {
if (node != null) {
this.in_order(node.left);
process.stdout.write(" " + node.data);
this.in_order(node.right);
}
}
pre_order(node) {
if (node != null) {
process.stdout.write(" " + node.data);
this.pre_order(node.left);
this.pre_order(node.right);
}
}
post_order(node) {
if (node != null) {
this.post_order(node.left);
this.post_order(node.right);
process.stdout.write(" " + node.data);
}
}
convert(head) {
if (head == null) {
return;
}
this.convert(head.left);
this.convert(head.right);
if (head.left == null) {
head.left = head.right;
} else {
head.left.right = head.right;
}
head.right = null;
}
}
function main() {
var obj = new BinaryTree();
/* Make A Binary Tree
---------------------
1
/ \
2 4
/ / \
3 6 5
\ / \ \
7 9 8 0
*/
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.left.left = new Node(3);
obj.root.left.left.right = new Node(7);
obj.root.right = new Node(4);
obj.root.right.right = new Node(5);
obj.root.right.right.right = new Node(0);
obj.root.right.left = new Node(6);
obj.root.right.left.left = new Node(9);
obj.root.right.left.right = new Node(8);
process.stdout.write("\n Before convert");
process.stdout.write("\nIn-order Data : ");
obj.in_order(obj.root);
process.stdout.write("\nPre-order Data : ");
obj.pre_order(obj.root);
process.stdout.write("\nPost-order Data : ");
obj.post_order(obj.root);
obj.convert(obj.root);
process.stdout.write("\n After convert");
process.stdout.write("\nIn-order Data : ");
obj.in_order(obj.root);
process.stdout.write("\nPre-order Data : ");
obj.pre_order(obj.root);
process.stdout.write("\nPost-order Data : ");
obj.post_order(obj.root);
}
main();
Output
Before convert
In-order Data : 3 7 2 1 9 6 8 4 5 0
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 2 9 8 6 0 5 4 1
After convert
In-order Data : 7 3 2 9 8 6 0 5 4 1
Pre-order Data : 1 2 3 7 4 6 9 8 5 0
Post-order Data : 7 3 8 9 0 5 6 4 2 1/*
Swift 4 Program
Convert left-right representation of a binary tree to down-right
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinaryTree {
var root: Node? ;
init() {
self.root = nil;
}
func in_order(_ node: Node? ) {
if (node != nil) {
self.in_order(node!.left);
print(node!.data, terminator:" ");
self.in_order(node!.right);
}
}
func pre_order(_ node: Node? ) {
if (node != nil) {
print(node!.data, terminator:" ");
self.pre_order(node!.left);
self.pre_order(node!.right);
}
}
func post_order(_ node: Node? ) {
if (node != nil) {
self.post_order(node!.left);
self.post_order(node!.right);
print(node!.data, terminator:" ");
}
}
func convert(_ head: Node? ) {
if (head == nil) {
return;
}
self.convert(head!.left);
self.convert(head!.right);
if (head!.left == nil) {
head!.left = head!.right;
} else {
head!.left!.right = head!.right;
}
head!.right = nil;
}
}
func main() {
let obj: BinaryTree = BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 4
/ / \
3 6 5
\ / \ \
7 9 8 0
*/
obj.root = Node(1);
obj.root!.left = Node(2);
obj.root!.left!.left = Node(3);
obj.root!.left!.left!.right = Node(7);
obj.root!.right = Node(4);
obj.root!.right!.right = Node(5);
obj.root!.right!.right!.right = Node(0);
obj.root!.right!.left = Node(6);
obj.root!.right!.left!.left = Node(9);
obj.root!.right!.left!.right = Node(8);
print("\n Before convert");
print("In-order Data : ");
obj.in_order(obj.root);
print("\nPre-order Data : ");
obj.pre_order(obj.root);
print("\nPost-order Data : ");
obj.post_order(obj.root);
obj.convert(obj.root);
print("\n After convert");
print("In-order Data : ");
obj.in_order(obj.root);
print("\nPre-order Data : ");
obj.pre_order(obj.root);
print("\nPost-order Data : ");
obj.post_order(obj.root);
}
main();
Output
Before convert
In-order Data :
3 7 2 1 9 6 8 4 5 0
Pre-order Data :
1 2 3 7 4 6 9 8 5 0
Post-order Data :
7 3 2 9 8 6 0 5 4 1
After convert
In-order Data :
7 3 2 9 8 6 0 5 4 1
Pre-order Data :
1 2 3 7 4 6 9 8 5 0
Post-order Data :
7 3 8 9 0 5 6 4 2 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