Q:

Program to convert a given binary tree to doubly linked list

belongs to collection: Doubly Linked List Programs

robaa
Save to bookmark
|
2022-11-10
|
  255 
0

Explanation

In this program, we need to convert the given binary tree to corresponding doubly liked list.

The binary tree is a tree data structure in which each node has at most two children node.

This can be achieved by traversing the tree in the in-order manner that is, left the child -> root ->right node. Traverse left sub-tree and convert it into the doubly linked list by adding nodes to the end of the list. In this way, leftmost node will become head of the list. Then, convert the right sub-tree into the doubly linked list.

Binary tree:

Corresponding doubly linked list:

Algorithm

  1. Define a Node class which represents a node in the binary tree. It will have three properties: data left, and right where the left and right represent two children of a node.
  2. Root will represent the root of the binary tree. Head and tail node represent the head and tail of the doubly linked list.
  3. BinaryTreeToDLL() will convert the given binary tree to corresponding doubly linked list.
    1. Perform inorder traversal of the binary tree by converting the left subtree first.
    2. If the list is empty, both head and tail will point to a node.
    3. If the list is not empty, the node will be inserted at the end of the list. Here, pointer left, and right will represent the previous and next pointer of the doubly linked list.
    4. Now, recursively call BinaryTreeToDLL() to convert the right subtree.
  4. display() will show all the nodes present in the list.
    1. Define a new node 'current' that will point to the head.
    2. Print current.data till current points to null.
    3. Current will point to the next node in the list in each iteration.

Input:

 

#Add nodes to the binary tree  

bt.root = Node(1);  

bt.root.left = Node(2);  

bt.root.right = Node(3);  

bt.root.left.left = Node(4);  

bt.root.left.right = Node(5);  

bt.root.right.left = Node(6);  

bt.root.right.right = Node(7);  

Output:

Nodes of generated doubly linked list: 4 2 5 1 6 3 7
Python programming, Php programming, Java programming, C programming, c# programming, examples, Python programming examples, Php programming examples, Java programming examples, C programming examples, c# programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-10
need an explanation for this answer? contact us directly to get an explanation for this answer

Python

#Represent a node of binary tree  
class Node:  
    def __init__(self,data):  
        self.data = data;  
        self.left = None;  
        self.right = None;  
          
class BinaryTreeToDLL:  
    def __init__(self):  
        #Represent the root of binary tree  
        self.root = None;  
        #Represent the head and tail of the doubly linked list  
        self.head = None;  
        self.tail = None;  
          
    #convertbtToDLL() will convert the given binary tree to corresponding doubly linked list  
    def convertbtToDLL(self, node):  
        #Checks whether node is None  
        if(node == None):  
            return;  
              
        #Convert left subtree to doubly linked list  
        self.convertbtToDLL(node.left);  
          
        #If list is empty, add node as head of the list  
        if(self.head == None):  
            #Both head and tail will point to node  
            self.head = self.tail = node;  
        #Otherwise, add node to the end of the list  
        else:  
            #node will be added after tail such that tail's right will point to node  
            self.tail.right = node;  
            #node's left will point to tail  
            node.left = self.tail;  
            #node will become new tail  
            self.tail = node;  
              
        #Convert right subtree to doubly linked list  
        self.convertbtToDLL(node.right);  
      
    #display() will print out the nodes of the list  
    def display(self):  
        #Node current will point to head  
        current = self.head;  
        if(self.head == None):  
            print("List is empty");  
            return;  
        print("Nodes of generated doubly linked list: ");  
        while(current != None):  
            #Prints each node by incrementing pointer.  
            print(current.data),  
            current = current.right;  
          
         
bt = BinaryTreeToDLL();  
#Add nodes to the binary tree  
bt.root = Node(1);  
bt.root.left = Node(2);  
bt.root.right = Node(3);  
bt.root.left.left = Node(4);  
bt.root.left.right = Node(5);  
bt.root.right.left = Node(6);  
bt.root.right.right = Node(7);  
   
#Converts the given binary tree to doubly linked list  
bt.convertbtToDLL(bt.root);  
   
#Displays the nodes present in the list  
bt.display();

 

Output:

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

 

C

#include <stdio.h>  
   
//Represent a node of the binary tree  
  
struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};      
   
//Represent the root of the binary tree  
  
struct node *root;  
      
//Represent the head and tail of the doubly linked list  
struct node *head, *tail = NULL;  
   
//createNode() will create a new node  
struct node* createNode(int data){  
    //Create a new node  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));  
    //Assign data to newNode, set left and right child to NULL  
    newNode->data = data;  
    newNode->left = NULL;  
    newNode->right = NULL;  
      
    return newNode;  
}  
   
//convertbtToDLL() will convert the given binary tree to corresponding doubly linked list  
void convertbtToDLL(struct node *node) {  
    //Checks whether node is NULL  
    if(node == NULL)  
        return;  
      
    //Convert left subtree to doubly linked list  
    convertbtToDLL(node->left);  
      
    //If list is empty, add node as head of the list  
    if(head == NULL) {  
        //Both head and tail will point to node  
        head = tail = node;  
    }  
    //Otherwise, add node to the end of the list  
    else {  
        //node will be added after tail such that tail's right will point to node  
        tail->right = node;  
        //node's left will point to tail  
        node->left = tail;  
        //node will become new tail  
        tail = node;  
    }  
      
    //Convert right subtree to doubly linked list  
    convertbtToDLL(node->right);  
}  
   
//display() will print out the nodes of the list  
void display() {  
    //Node current will point to head  
    struct node *current = head;  
    if(head == NULL) {  
        printf("List is empty\n");  
        return;  
    }  
    printf("Nodes of generated doubly linked list: \n");  
    while(current != NULL) {  
        //Prints each node by incrementing pointer.  
        printf("%d ",current->data);  
        current = current->right;  
    }  
    printf("\n");  
}  
      
int main()  
{  
    //Add nodes to the binary tree  
    root = createNode(1);  
    root->left = createNode(2);  
    root->right = createNode(3);  
    root->left->left = createNode(4);  
    root->left->right = createNode(5);  
    root->right->left = createNode(6);  
    root->right->right = createNode(7);  
      
    //Converts the given binary tree to doubly linked list  
    convertbtToDLL(root);  
      
    //Displays the nodes present in the list  
    display();      
   
    return 0;  
}

 

Output:

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

 

JAVA

public class BinaryTreeToDLL {  
       //Represent a node of the binary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
          
        public Node(int data) {  
            this.data = data;  
            this.left = null;  
            this.right = null;  
        }  
    }  
      
    //Represent the root of the binary tree  
  
    public Node root;  
        
    //Represent the head and tail of the doubly linked list  
    Node head, tail = null;  
      
    //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list  
    public void convertbtToDLL(Node node) {  
        //Checks whether node is null  
        if(node == null)  
            return;  
          
        //Convert left subtree to doubly linked list  
        convertbtToDLL(node.left);  
          
        //If list is empty, add node as head of the list  
        if(head == null) {  
            //Both head and tail will point to node  
            head = tail = node;  
        }  
        //Otherwise, add node to the end of the list  
        else {  
            //node will be added after tail such that tail's right will point to node  
            tail.right = node;  
            //node's left will point to tail  
            node.left = tail;  
            //node will become new tail  
            tail = node;  
        }  
          
        //Convert right subtree to doubly linked list  
        convertbtToDLL(node.right);  
    }  
      
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        System.out.println("Nodes of generated doubly linked list: ");  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.right;  
        }  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
          
        BinaryTreeToDLL bt = new BinaryTreeToDLL();  
        //Add nodes to the binary tree  
        bt.root = new Node(1);  
        bt.root.left = new Node(2);  
        bt.root.right = new Node(3);  
        bt.root.left.left = new Node(4);  
        bt.root.left.right = new Node(5);  
        bt.root.right.left = new Node(6);  
        bt.root.right.right = new Node(7);  
          
        //Converts the given binary tree to doubly linked list  
        bt.convertbtToDLL(bt.root);  
          
        //Displays the nodes present in the list  
        bt.display();  
    }  
}

 

Output:

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

 

C#

using System;   
namespace DoublyLinkedList   
{                       
    public class Program  
    {  
        //Represent a node of the binary tree  
  
        public class Node<T>{  
            public T data;  
            public Node<T> left;  
            public Node<T> right;  
              
            public Node(T value) {  
                data = value;  
                left = null;  
                right = null;  
            }  
        }  
          
        public class BinaryTreeToDLL<T>{  
            //Represent the root of the binary tree  
  
            public Node<T> root;  
              
            //Represent the head and tail of the doubly linked list  
            public Node<T> head = null;               
             public Node<T> tail = null;  
              
            //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list  
            public void convertbtToDLL(Node<T> node) {  
                //Checks whether node is null  
                if(node == null)  
                    return;  
   
                //Convert left subtree to doubly linked list  
                convertbtToDLL(node.left);  
   
                //If list is empty, add node as head of the list  
                if(head == null) {  
                    //Both head and tail will point to node  
                    head = tail = node;  
                }  
                //Otherwise, add node to the end of the list  
                else {  
                    //node will be added after tail such that tail's right will point to node  
                    tail.right = node;  
                    //node's left will point to tail  
                    node.left = tail;  
                    //node will become new tail  
                    tail = node;  
                }  
   
                //Convert right subtree to doubly linked list  
                convertbtToDLL(node.right);  
            }  
      
            //display() will print out the nodes of the list  
            public void display() {  
                //Node current will point to head  
                Node<T> current = head;  
                if(head == null) {  
                    Console.WriteLine("List is empty");  
                    return;  
                }  
                Console.WriteLine("Nodes of generated doubly linked list: ");  
                while(current != null) {  
                    //Prints each node by incrementing the pointer.  
  
                    Console.Write(current.data + " ");  
                    current = current.right;  
                }  
                Console.WriteLine();  
            }  
        }  
          
        public static void Main()  
        {  
            BinaryTreeToDLL<int> bt = new BinaryTreeToDLL<int>();  
            //Add nodes to the binary tree  
            bt.root = new Node<int>(1);  
            bt.root.left = new Node<int>(2);  
            bt.root.right = new Node<int>(3);  
            bt.root.left.left = new Node<int>(4);  
            bt.root.left.right = new Node<int>(5);  
            bt.root.right.left = new Node<int>(6);  
            bt.root.right.right = new Node<int>(7);  
   
            //Converts the given binary tree to doubly linked list  
            bt.convertbtToDLL(bt.root);  
   
            //Displays the nodes present in the list  
            bt.display();  
        }      
    }  
}

 

Output:

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

 

PHP

<!DOCTYPE html>  
<html>  
<body>  
<?php  
//Represent a node of binary tree  
class Node{  
    public $data;  
    public $left;  
    public $right;  
      
    function __construct($data){  
        $this->data = $data;  
        $this->left = NULL;  
        $this->right = NULL;  
    }  
}  
class BinaryTreeToDLL{  
    //Represent the root of binary tree  
    public $root;  
    //Represent the head and tail of the doubly linked list  
    public $head;  
    public $tail;  
    function __construct(){  
        $this->head = NULL;  
        $this->tail = NULL;  
        $this->root = NULL;  
    }  
      
    //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list  
    function convertbtToDLL($node) {  
        //Checks whether node is null  
        if($node == NULL)  
            return;  
          
        //Convert left subtree to doubly linked list  
        $this->convertbtToDLL($node->left);  
          
        //If list is empty, add node as head of the list  
        if($this->head == NULL) {  
            //Both head and tail will point to node  
            $this->head = $this->tail = $node;  
        }  
        //Otherwise, add node to the end of the list  
        else {  
            //node will be added after tail such that tail's right will point to node  
            $this->tail->right = $node;  
            //node's left will point to tail  
            $node->left = $this->tail;  
            //node will become new tail  
            $this->tail = $node;  
        }  
          
        //Convert right subtree to doubly linked list  
        $this->convertbtToDLL($node->right);  
    }  
      
    //display() will print out the nodes of the list  
    function display() {  
        //Node current will point to head  
        $current = $this->head;  
        if($this->head == NULL) {  
            print("List is empty <br>");  
            return;  
        }  
        print("Nodes of generated doubly linked list: <br>");  
        while($current != NULL) {  
            //Prints each node by incrementing pointer.  
            print($current->data . " ");  
            $current = $current->right;  
        }  
        print("<br>");  
    }  
}  
      
$bt = new BinaryTreeToDLL();  
//Add nodes to the binary tree  
$bt->root= new Node(1);  
$bt->root->left = new Node(2);  
$bt->root->right = new Node(3);  
$bt->root->left->left = new Node(4);  
$bt->root->left->right = new Node(5);  
$bt->root->right->left = new Node(6);  
$bt->root->right->right = new Node(7);  
   
//Converts the given binary tree to doubly linked list  
$bt->convertbtToDLL($bt->root);  
   
//Displays the nodes present in the list  
$bt->display();  
?>  
</body>  
</html>

 

Output:

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Doubly Linked List Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Program to create a doubly linked list from a Tern... >>