fork download
copy 
  1. #include <stdexcept>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. struct node {
  7.     int val;
  8.     struct node *left;
  9.     struct node *right;
  10. };
  11.  
  12. void inorder(struct node *root) {
  13.     if (!root) {
  14.         return;
  15.     }
  16.     inorder(root->left);
  17.     cout << root->val << " ";
  18.     inorder(root->right);
  19. }
  20.  
  21. void traverse_dll(struct node *start, struct node *end) {
  22.     if(!start || !end ||start->left || end->right) {
  23.         throw invalid_argument("Invalid doubly linked list passed");
  24.     }
  25.     struct node *t;
  26.     for(t = start; t != end; t = t->right) {
  27.         cout << t->val << " ";
  28.     }
  29.     cout << t->val << endl;
  30.     for(t = end; t != start; t = t->left) {
  31.         cout << t->val << " ";
  32.     }
  33.     cout << t->val <<endl;
  34. }
  35.  
  36. void convert(struct node *root, struct node **start, struct node **end) {
  37.  
  38.     if (!root || !start || !end) {
  39.         // raise an exception if no root is found
  40.         // or if other ptrs are bad
  41.         throw invalid_argument("Invalid pointers passed");
  42.     }
  43.  
  44.     // convert left sub-tree into doubly linked list
  45.     // start of left dll = left_start, end of dll = left_end
  46.     struct node *left_start, *left_end;
  47.     struct node *left_child = root->left;
  48.     // if there's a left child
  49.     if (left_child) {
  50.         // recursively convert left child
  51.         convert(left_child, &left_start, &left_end);
  52.         // join left_end and root
  53.         left_end->right = root;
  54.         root->left = left_end;
  55.     } else {
  56.         // no left child, make root as left_start
  57.         // Notice that we have no need to populate the left_end
  58.         left_start = root;
  59.     }
  60.  
  61.     // similarly for right child...
  62.     struct node *right_start, *right_end;
  63.     struct node *right_child = root->right;
  64.     //if there's a right child
  65.     if (right_child) {
  66.         // recurisvely convert right child
  67.         convert(right_child, &right_start, &right_end);
  68.         // join root and right_start
  69.         root->right = right_start;
  70.         right_start->left = root;
  71.     } else {
  72.         // no right child, make root as right_end
  73.         // notice that we have no need to populate
  74.         // right_start in this case
  75.         right_end = root;
  76.     }
  77.  
  78.     // populate the start and end double pointers with
  79.     // start and end of doubly linked lists...
  80.     *start = left_start;
  81.     *end = right_end;
  82. }
  83.  
  84. int main() {
  85.     // construct a bst [3 to 17]
  86.     struct node lll = {3, nullptr, nullptr};
  87.     struct node llr = {5, nullptr, nullptr};
  88.     struct node lrl = {7, nullptr, nullptr};
  89.     struct node lrr = {9, nullptr, nullptr};
  90.     struct node rll = {11, nullptr, nullptr};
  91.     struct node rlr = {13, nullptr, nullptr};
  92.     struct node rrl = {15, nullptr, nullptr};
  93.     struct node rrr = {17, nullptr, nullptr};
  94.     struct node ll = {4, &lll, &llr};
  95.     struct node lr = {8, &lrl, &lrr};
  96.     struct node rl = {12, &rll, &rlr};
  97.     struct node rr = {16, &rrl, &rrr};
  98.     struct node l = {6, &ll, &lr};
  99.     struct node r = {14, &rl, &rr};
  100.     struct node root = {10, &l, &r};
  101.     // print inorder
  102.     inorder(&root); cout << endl;
  103.     // convert bst to dll
  104.     struct node *start, *end;
  105.     convert(&root, &start, &end);
  106.     // print doubly linked list
  107.     traverse_dll(start, end);
  108. }
  109.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3
https://ideone.com/EAIJPH
Convert a binary search tree to a doubly linked list
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!