Post
Ask Question

Binary Tree To Double Linked List

Introduction

 
In this article we will discuss about a popular interview question, which is how would you convert a binary tree to a double linked list. Now, a binary tree is a hierachical graph data structure and that does makes binary search tree a part of the question, it just needs to be a binary tree. And a double linked list is a data structure where nodes that hold information are sequentially chained, each node holds a pointer to the next node in the chain.
 
Binary Tree to Double Linked List
 

Algorithm

 
We will choose the most naive approach for solving the problem. We'll do an in order traversal of the binary tree which ends up visiting the nodes in the order: 25 12 30 100, which is the order we want our double linked list to have. We'll keep track of the current node that we're looking at, and the previous node that we've visited. At each step, we'll make the current root node's left pointer point to the previous node, and we'll make the previous node's right pointer point to the current root node. We'll also cover one specific case where our first node becomes the previous node, and we have a head pointer for our linked list point to that node. Here is the C++ algorithm,
  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. struct Node {  
  5.     int Data;  
  6.     struct Node* Left;  
  7.     struct Node* Right;  
  8.       
  9.     Node(int data) {  
  10.         this->Data = data;  
  11.         this->Left = NULL;  
  12.         this->Right = NULL;  
  13.     }  
  14. };  
  15. void PrintDoubleLinkedList(Node* head) {  
  16.     // for last nodes  
  17.     if(head == NULL) {   
  18.         cout << endl;   
  19.         return;   
  20.     }  
  21.       
  22.     // print node  
  23.     cout << head->Data << " ";  
  24.       
  25.     // recursively print   
  26.     PrintDoubleLinkedList(head->Right);  
  27. }  
  28. void ParseBinaryTree(Node* root, Node*& previous, Node*& header) {  
  29.     if(root == NULL) {   
  30.         return;   
  31.     }  
  32.       
  33.     // for left nodes  
  34.     ParseBinaryTree(root->Left, previous, header);  
  35.       
  36.     if(previous == NULL) {  
  37.         // Set the header & previous node for the first node  
  38.         header = root;  
  39.         previous = root;  
  40.     }  
  41.     else{  
  42.         // root node's left pointer point to the previous node  
  43.         root->Left = previous;  
  44.           
  45.         // previous node's right pointer point to the root  
  46.         previous->Right = root;  
  47.               
  48.         // update the previous node  
  49.         previous = root;  
  50.     }  
  51.           
  52.     // for right nodes  
  53.     ParseBinaryTree(root->Right, previous, header);  
  54. }  
  55. int main() {  
  56.     // initailize a binary tree  
  57.     Node* root = new Node(100);  
  58.     root->Left = new Node(12);  
  59.     root->Left->Left = new Node(25);  
  60.     root->Left->Right = new Node(30);  
  61.       
  62.     // intialize null header & prvious node nodes  
  63.     Node* header = NULL;  
  64.     Node* prevNode = NULL;  
  65.       
  66.     // parse binary tree to linked list  
  67.     ParseBinaryTree(root, prevNode, header);  
  68.       
  69.     cout << "DOUBLE LINKED LIST : ";  
  70.     // print the link list  
  71.     PrintDoubleLinkedList(header);  
  72.           
  73.     return 0;  
  74. }  
The time complexity is O(N), as we visit each node exactly once, and the space complexity is O(1), since we use no extra space.