Convert a given binary tree to Doubly Linked List
Here given code implementation process.
/*
C Program
Convert a given binary tree to Doubly Linked List
//using recursion
*/
#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* insert(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 change(struct Node *head, struct Node *leftP, struct Node *rightP) {
if (head != NULL) {
change(head->left, leftP, head);
change(head->right, head, rightP);
if (head->left == NULL) {
head->left = leftP;
if (leftP != NULL) {
leftP->right = head;
}
}
if (head->right == NULL) {
head->right = rightP;
if (rightP != NULL) {
rightP->left = head;
}
}
}
}
void showDDL(struct Node *root) {
struct Node *head = root;
if (head != NULL) {
while (head != NULL) {
printf(" %d",head->data);
head = head->right;
}
}
}
void doublyList(struct Node **root) {
if (*root != NULL) {
change(*root, NULL, NULL);
while ((*root)->left != NULL) {
*root = (*root)->left;
}
}
}
int main()
{
struct Node*root=NULL;
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\ \
7 9
/
8
*/
root = insert(1);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(6);
root->right->left = insert(5);
root->right->left->right = insert(9);
root->left->left = insert(4);
root->left->left->right = insert(7);
root->left->left->right->left = insert(8);
doublyList(&root);
showDDL(root);
return 0;
}
Output
4 8 7 2 1 5 9 3 6/*
C++ Program
Convert a given binary tree to Doubly Linked List
//using recursion
*/
#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 change(Node *head, Node *leftP, Node *rightP) {
if (head != NULL) {
this->change(head->left, leftP, head);
this->change(head->right, head, rightP);
if (head->left == NULL) {
head->left = leftP;
if (leftP != NULL) {
leftP->right = head;
}
}
if (head->right == NULL) {
head->right = rightP;
if (rightP != NULL) {
rightP->left = head;
}
}
}
}
void showDDL() {
Node *head = this->root;
if (head != NULL) {
cout << ("\n");
while (head != NULL) {
cout << " " << head->data;
head = head->right;
}
}
}
void doublyList(Node *head) {
if (head != NULL) {
this->change(head, NULL, NULL);
while (this->root->left != NULL) {
this->root = this->root->left;
}
}
}
};
int main() {
BinaryTree obj;
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\ \
7 9
/
8
*/
obj.root = new Node(1);
obj.root->left = new Node(2);
obj.root->right = new Node(3);
obj.root->right->right = new Node(6);
obj.root->right->left = new Node(5);
obj.root->right->left->right = new Node(9);
obj.root->left->left = new Node(4);
obj.root->left->left->right = new Node(7);
obj.root->left->left->right->left = new Node(8);
obj.doublyList(obj.root);
obj.showDDL();
return 0;
}
Output
4 8 7 2 1 5 9 3 6/*
Java Program
Convert a given binary tree to Doubly Linked List
//using recursion
*/
//Structure 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 tree root to null
root = null;
}
//Function which is convert binary tree to DLL
public void change(Node head, Node leftP, Node rightP) {
if (head != null) {
change(head.left, leftP, head);
change(head.right, head, rightP);
if (head.left == null) {
head.left = leftP;
if (leftP != null) {
leftP.right = head;
}
}
if (head.right == null) {
head.right = rightP;
if (rightP != null) {
rightP.left = head;
}
}
}
}
//Display data in doubly linked list
public void showDDL() {
Node head = root;
if (head != null) {
System.out.println();
while (head != null) {
System.out.print(" " + head.data);
head = head.right;
}
}
}
public void doublyList(Node head) {
if (head != null) {
//Covert into Doubly linked list
change(head, null, null);
//reset root to first inorder node
while (root.left != null) {
//Set root node
root = root.left;
}
}
}
public static void main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\ \
7 9
/
8
*/
//Add binary tree elements
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.right.left.right = new Node(9);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.left.left.right.left = new Node(8);
obj.doublyList(obj.root);
obj.showDDL();
}
}
Output
4 8 7 2 1 5 9 3 6/*
C# Program
Convert a given binary tree to Doubly Linked List
//using recursion
*/
using System;
//Structure 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 tree root to null
root = null;
}
//Function which is convert binary tree to DLL
public void change(Node head, Node leftP, Node rightP) {
if (head != null) {
change(head.left, leftP, head);
change(head.right, head, rightP);
if (head.left == null) {
head.left = leftP;
if (leftP != null) {
leftP.right = head;
}
}
if (head.right == null) {
head.right = rightP;
if (rightP != null) {
rightP.left = head;
}
}
}
}
//Display data in doubly linked list
public void showDDL() {
Node head = root;
if (head != null) {
Console.WriteLine();
while (head != null) {
Console.Write(" " + head.data);
head = head.right;
}
}
}
public void doublyList(Node head) {
if (head != null) {
//Covert into Doubly linked list
change(head, null, null);
//reset root to first inorder node
while (root.left != null) {
//Set root node
root = root.left;
}
}
}
public static void Main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\ \
7 9
/
8
*/
//Add binary tree elements
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.right.left.right = new Node(9);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.left.left.right.left = new Node(8);
obj.doublyList(obj.root);
obj.showDDL();
}
}
Output
4 8 7 2 1 5 9 3 6# Python Program
# Convert a given binary tree to Doubly Linked List
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def change(self, head, leftP, rightP) :
if (head != None) :
self.change(head.left, leftP, head)
self.change(head.right, head, rightP)
if (head.left == None) :
head.left = leftP
if (leftP != None) :
leftP.right = head
if (head.right == None) :
head.right = rightP
if (rightP != None) :
rightP.left = head
def showDDL(self) :
head = self.root
if (head != None) :
print()
while (head != None) :
print(head.data,end=" ")
head = head.right
def doublyList(self, head) :
if (head != None) :
self.change(head, None, None)
while (self.root.left != None) :
self.root = self.root.left
def main() :
obj = BinaryTree()
# Make A Binary Tree
# 1
# / \
# 2 3
# / / \
# 4 5 6
# \ \
# 7 9
# /
# 8
#
obj.root = Node(1)
obj.root.left = Node(2)
obj.root.right = Node(3)
obj.root.right.right = Node(6)
obj.root.right.left = Node(5)
obj.root.right.left.right = Node(9)
obj.root.left.left = Node(4)
obj.root.left.left.right = Node(7)
obj.root.left.left.right.left = Node(8)
obj.doublyList(obj.root)
obj.showDDL()
if __name__ == "__main__":
main()
Output
4 8 7 2 1 5 9 3 6# Ruby Program
# Convert a given binary tree to Doubly Linked List
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 change(head, leftP, rightP)
if (head != nil)
self.change(head.left, leftP, head)
self.change(head.right, head, rightP)
if (head.left == nil)
head.left = leftP
if (leftP != nil)
leftP.right = head
end
end
if (head.right == nil)
head.right = rightP
if (rightP != nil)
rightP.left = head
end
end
end
end
def showDDL()
head = @root
if (head != nil)
print("\n")
while (head != nil)
print(" ", head.data)
head = head.right
end
end
end
def doublyList(head)
if (head != nil)
self.change(head, nil, nil)
while (@root.left != nil)
@root = @root.left
end
end
end
end
def main()
obj = BinaryTree.new()
# Make A Binary Tree
# 1
# / \
# 2 3
# / / \
# 4 5 6
# \ \
# 7 9
# /
# 8
#
obj.root = Node.new(1)
obj.root.left = Node.new(2)
obj.root.right = Node.new(3)
obj.root.right.right = Node.new(6)
obj.root.right.left = Node.new(5)
obj.root.right.left.right = Node.new(9)
obj.root.left.left = Node.new(4)
obj.root.left.left.right = Node.new(7)
obj.root.left.left.right.left = Node.new(8)
obj.doublyList(obj.root)
obj.showDDL()
end
main()
Output
4 8 7 2 1 5 9 3 6<?php
/*
Php Program
Convert a given binary tree to Doubly Linked List
*/
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 change($head, $leftP, $rightP) {
if ($head != null) {
$this->change($head->left, $leftP, $head);
$this->change($head->right, $head, $rightP);
if ($head->left == null) {
$head->left = $leftP;
if ($leftP != null) {
$leftP->right = $head;
}
}
if ($head->right == null) {
$head->right = $rightP;
if ($rightP != null) {
$rightP->left = $head;
}
}
}
}
public function showDDL() {
$head = $this->root;
if ($head != null) {
echo("\n");
while ($head != null) {
echo(" ".$head->data);
$head = $head->right;
}
}
}
public function doublyList($head) {
if ($head != null) {
$this->change($head, null, null);
while ($this->root->left != null) {
$this->root = $this->root->left;
}
}
}
}
function main() {
$obj = new BinaryTree();
$obj->root = new Node(1);
$obj->root->left = new Node(2);
$obj->root->right = new Node(3);
$obj->root->right->right = new Node(6);
$obj->root->right->left = new Node(5);
$obj->root->right->left->right = new Node(9);
$obj->root->left->left = new Node(4);
$obj->root->left->left->right = new Node(7);
$obj->root->left->left->right->left = new Node(8);
$obj->doublyList($obj->root);
$obj->showDDL();
}
main();
Output
4 8 7 2 1 5 9 3 6/*
Node JS Program
Convert a given binary tree to Doubly Linked List
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
};
class BinaryTree {
constructor() {
this.root = null;
}
change(head, leftP, rightP) {
if (head != null) {
this.change(head.left, leftP, head);
this.change(head.right, head, rightP);
if (head.left == null) {
head.left = leftP;
if (leftP != null) {
leftP.right = head;
}
}
if (head.right == null) {
head.right = rightP;
if (rightP != null) {
rightP.left = head;
}
}
}
}
showDDL() {
var head = this.root;
if (head != null) {
process.stdout.write();
while (head != null) {
process.stdout.write(" " + head.data);
head = head.right;
}
}
}
doublyList(head) {
if (head != null) {
this.change(head, null, null);
while (this.root.left != null) {
this.root = this.root.left;
}
}
}
}
function main() {
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\ \
7 9
/
8
*/
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.right.left.right = new Node(9);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.left.left.right.left = new Node(8);
obj.doublyList(obj.root);
obj.showDDL();
}
main();
Output
4 8 7 2 1 5 9 3 6/*
Swift 4 Program
Convert a given binary tree to Doubly Linked List
*/
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 change(_ head: Node? , _ leftP : Node? , _ rightP : Node? ) {
if (head != nil) {
self.change(head!.left, leftP, head);
self.change(head!.right, head, rightP);
if (head!.left == nil) {
head!.left = leftP;
if (leftP != nil) {
leftP!.right = head;
}
}
if (head!.right == nil) {
head!.right = rightP;
if (rightP != nil) {
rightP!.left = head;
}
}
}
}
func showDDL() {
var head: Node? = self.root;
if (head != nil) {
while (head != nil) {
print(head!.data, terminator : " ");
head = head!.right;
}
}
}
func doublyList(_ head: Node? ) {
if (head != nil) {
self.change(head, nil, nil);
while (self.root!.left != nil) {
self.root = self.root!.left;
}
}
}
}
func main() {
let obj: BinaryTree = BinaryTree();
/* Make A Binary Tree
-----------------------
1
/ \
2 3
/ / \
4 5 6
\ \
7 9
/
8
*/
obj.root = Node(1);
obj.root!.left = Node(2);
obj.root!.right = Node(3);
obj.root!.right!.right = Node(6);
obj.root!.right!.left = Node(5);
obj.root!.right!.left!.right = Node(9);
obj.root!.left!.left = Node(4);
obj.root!.left!.left!.right = Node(7);
obj.root!.left!.left!.right!.left = Node(8);
obj.doublyList(obj.root);
obj.showDDL();
}
main();
Output
4 8 7 2 1 5 9 3 6
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