Program to Convert a Given Binary Tree to Doubly Linked List

Q. Program to convert a given binary tree to doubly linked list.

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:

Program to convert a given binary tree to doubly linked list

Corresponding doubly linked list:

Program to convert a given binary tree to doubly linked list

Algorithm

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.
Root will represent the root of the binary tree. Head and tail node represent the head and tail of the doubly linked list.
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.
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.

Solution

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 emptyn”);          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

Next Topic#

Q. Program to convert a given binary tree to doubly linked list.

Explanation

Algorithm

Solution

Python

C

JAVA

C#

PHP

Potential Energy

Program to Find The Transpose of a Given Matrix

You may also like