{"id":3487,"date":"2021-08-03T09:19:26","date_gmt":"2021-08-03T09:19:26","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3487"},"modified":"2022-12-13T11:26:43","modified_gmt":"2022-12-13T11:26:43","slug":"convert-a-given-binary-tree-to-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/convert-a-given-binary-tree-to-doubly-linked-list\/","title":{"rendered":"Convert a given Binary Tree to Doubly Linked List"},"content":{"rendered":"

\"\"<\/p>\n

This article will discuss in detail how to convert binary tree to doubly linked list. Conversion of binary tree to doubly linked list is an amazing task, which will improve your data structures skills that will help you to achieve your aim. Let\u2019s discuss how to convert convert binary tree to doubly linked list.<\/p>\n

How To Convert Binary Tree To Doubly Linked List<\/h2>\n

In this problem, we are given a binary tree. We have to convert the given binary tree to a doubly-linked list.<\/p>\n

We have to store the inorder traversal of the given binary tree in the newly created linked list. <\/p>\n

Sample Input:<\/strong><\/p>\n

\"\"<\/p>\n

Sample Output:<\/strong><\/p>\n

\"\"<\/p>\n

Explanation:<\/h2>\n

The output doubly linked list contains the in-order traversal of the given binary tree.<\/p>\n

We should note that the order of the nodes in the doubly linked list must be the same as the in-order traversal of the binary tree. The first node of the in-order traversal must be the head of the doubly linked list. The left and right pointers will be used as previous and next pointers, respectively. Let us have a glance at the approach.<\/p>\n

Approach#1 To Convert Binary Tree To Doubly Linked List<\/h2>\n

In this approach, we will traverse do an inorder traversal of the binary tree. We will add the nodes at the beginning of the newly created linked list, and update the head every time. But there is a problem. Since we will insert at beginning, the order or the linked list that we will recieve, will be reversed.<\/p>\n

To correct that, we can do a reverse inorder traversal of the tree, i.e. we will traverse through the right subtree before the left subtree.<\/p>\n

Algorithm To Convert Binary Tree To Doubly Linked List<\/h2>\n
    \n
  • Base Case – If the root is NULL, then simply return.<\/li>\n
  • Recur for the right subtree.<\/li>\n
  • Make the current root\u2019s right point to head, and head\u2019s left pointer to the the current root. By doing this, we are adding the current root to the head , and make the current root the head.<\/li>\n
  • After the above step, recur for the left subtree.<\/li>\n
  • Recursively, the tree will be traversed and the doubly linked list will be created as discussed.<\/li>\n<\/ul>\n

    Dry run To Convert Binary Tree To Doubly Linked List<\/h3>\n

    \"\"<\/p>\n

    Code Implementation To Convert Binary Tree To Doubly Linked List<\/h2>\n\t\t\t\t\t\t