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;
  4. struct Node {
  5. int Data;
  6. struct Node* Left;
  7. struct Node* Right;
  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. }
  22. // print node
  23. cout << head->Data << " ";
  25. // recursively print
  26. PrintDoubleLinkedList(head->Right);
  27. }
  28. void ParseBinaryTree(Node* root, Node*& previous, Node*& header) {
  29. if(root == NULL) {
  30. return;
  31. }
  33. // for left nodes
  34. ParseBinaryTree(root->Left, previous, header);
  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;
  45. // previous node's right pointer point to the root
  46. previous->Right = root;
  48. // update the previous node
  49. previous = root;
  50. }
  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);
  62. // intialize null header & prvious node nodes
  63. Node* header = NULL;
  64. Node* prevNode = NULL;
  66. // parse binary tree to linked list
  67. ParseBinaryTree(root, prevNode, header);
  69. cout << "DOUBLE LINKED LIST : ";
  70. // print the link list
  71. PrintDoubleLinkedList(header);
  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.