Binary Tree to Doubly Linked List

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

Binary Trees are a type of data structure where each data is stored as a node, and each node has two child nodes. The three primary traversal techniques are pre-order, in-order, and post-order. 

Linked Lists are another type of data structure where data is stored in nodes, and each node is connected via links. A linked list can be singly linked or doubly-linked depending upon the number of links. The two pointers in a doubly-linked list are: next and previous. 

In this article, we will learn to convert a given binary tree into a doubly-linked list by performing in-order traversal. To know more about the various tree traversals, click here Tree Traversals.

Problem Statement

Given a binary tree with nodes, convert it into a doubly-linked list. 

Note: Store the inorder traversal of the given binary tree to the doubly linked list.

Example

Sample Input

 

 

Expected Output

Approach and Explanation

The implementation of the given problem is done in Java. 

The step-by-step explanation is as follows - 

  • Binary Tree and Linked List are abstract data structures. This means that we need to create/define them so that we can use them.
     
  • We create a constructor named TLL. It has three members- data(int), left(TLL), and right(TLL). The variable data contains the node’s value and left and right are the links that will connect the nodes.
     
  • Once this is done, create a class that will do all our work and convert the binary tree into a linked list. Inside this class, have two global variables named root and head of the constructor type (TLL in our case) to perform the in-place conversion.
     
  • Create a function that will recursively convert a Binary Tree node into a node of the Doubly Linked List. Name this function as createDLL().
     
  • The variable root is for our binary tree, and the variable head is for our doubly linked list. 
     
  • The base case of the recursion is that if the root is null, we simply return and end the recursion. Else we recur for the right sub-tree first and set its value to the head of our linked list. 
     
  • We then check if the head is null or not. If it is not null, then the left side of the head contains the root. After assigning the value of root in the head, we traverse the left sub-tree.
     
  • In the given implementation, there are two print functions. One of them is for the linked list, and the other is for the binary tree.
     
  • In the function printLL(TLL head), we pass the head node of our linked list and print by traversing the whole list.
     
  • In the function printBT(TLL root), we pass the root of our binary tree, perform level order traversal and print the tree level-wise. 
     
  • Inside our main() function, we create our binary tree object and pass some values for our nodes and then call the following three functions:
    • printBT(): To print the binary tree given as the input.
    • createDLL(): To create a doubly-linked list from the binary tree.
    • printLL(): To print the doubly-linked list.

 

Recommended: Try to solve the problem first on our CodeStudio by clicking here Convert A Given Binary Tree To Doubly Linked List

Java implementation

import java.util.*;

class TLL{
  int data;
  TLL left,right;

  public TLL(int value){
      data = value;
      left = right = null;
  }
}

public class BTreeDLL {
  TLL root;
  TLL head;

  void createDLL(TLL root)
  {
      if (root == null)
          return;
      createDLL(root.right);

      root.right = head;

      if (head != null)
          head.left = root;
      head = root;

      createDLL(root.left);
  }

  void printLL(TLL head)
  {
      while (head != null) {
          System.out.print(head.data + " ");
          head = head.right;
      }
  }

  void printBT(TLL root){
      if(root == null)
          return;
      Queue<TLL> q =new LinkedList<TLL>();

      q.add(root);
      while(true)
      {
          int nC = q.size();
          if(nC == 0)
              break;
          while(nC > 0)
          {
              TLL node = q.peek();
              System.out.print(node.data + " ");
              q.remove();
              if(node.left != null)
                  q.add(node.left);
              if(node.right != null)
                  q.add(node.right);
              nC--;
          }
          System.out.println();
      }
  }

  public static void main(String[] args){

      BTreeDLL tree = new BTreeDLL();
      tree.root = new TLL(5);
      tree.root.left = new TLL(7);
      tree.root.right = new TLL(9);
      tree.root.left.left = new TLL(11);
      tree.root.left.right = new TLL(13);
      tree.root.right.left = new TLL(17);

      System.out.println("The Binary Tree is:");
      tree.printBT(tree.root);

      tree.createDLL(tree.root);

      System.out.print("The Linked List Formed: ");
      tree.printLL(tree.head);
  }
}

 

OUTPUT

The Binary Tree is:
5 
7 9 
11 13 17 
The Linked List Formed: 11 7 13 5 17 9 

Complexities

Time Complexity

We traverse our binary tree of n nodes once in the given implementation to create our doubly linked list. Thus time complexity is:

T(n) = O(n)

where n is the number of nodes.

Space Complexity

In the given implementation, we use recursion to make our doubly linked list. Thus, 

Space Complexity = O(h)

O(h) is the extra space for the recursion stack, where h is the height of the binary tree.

Frequently Asked Questions

  1. Are there other ways to convert a binary tree into a doubly-linked list?
    Yes, there are a few more ways to convert a binary tree into a doubly-linked list. One of them is to perform in-order traversal, keep track of the visited nodes of our linked list and insert each visited node at the tail of our linked list.
     
  2. Are these problems asked in coding interviews?
    Yes, such questions are asked in the coding interviews of various companies like AdobeFacebook, and  Google. You can practice various coding interview problems and read about many interview experiences on our CodeStudio

Key Takeaways

In a nutshell, this article discussed the conversion of a binary tree to a doubly-linked list thoroughly. We saw the problem statement, an example, an approach to the problem, its Java implementation, and the time and space complexities. We concluded the article with a few FAQs.

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.
Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our Library.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think