fork(3) download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class Node {
  5. public:
  6.     int data;
  7.     Node *left, *right, *next;
  8.     Node(int data) {
  9.         this->data = data;
  10.         left = NULL;
  11.         right = NULL;
  12.         next = NULL;
  13.     }
  14.     ~Node() {
  15.         delete left;
  16.         delete right;
  17.         left = NULL;
  18.         right = NULL;
  19.     }
  20. };
  21.  
  22. class Tree {
  23. private:
  24.     Node *root;
  25.  
  26.     class maxMin {
  27.     public:
  28.         Node *max;
  29.         Node *min;
  30.         maxMin() {}
  31.         maxMin(maxMin left, maxMin right, Node *root) {
  32.             this->min = left.min;
  33.             this->max = right.max;
  34.             if(this->max == NULL)
  35.                 this->max = root;
  36.             if(this->min == NULL)
  37.                 this->min = root;
  38.         }
  39.     };
  40.  
  41.     maxMin convertBSTtoDLLUtil(Node *root) {
  42.         if(root == NULL) {
  43.             maxMin a;
  44.             a.max = NULL;
  45.             a.min = NULL;
  46.             return a;
  47.         }
  48.         maxMin left = convertBSTtoDLLUtil(root->left);
  49.         maxMin right = convertBSTtoDLLUtil(root->right);
  50.         if(left.max != NULL) {
  51.             (left.max)->right = root;
  52.         }
  53.         root->left = left.max;
  54.         if(right.min != NULL) {
  55.             (right.min)->left = root;
  56.         }
  57.         root->right = right.min;
  58.         maxMin returnVal(left, right, root);
  59.         return returnVal;
  60.     }
  61.  
  62. public:
  63.  
  64.     Tree() {
  65.         //        cout << "In Constructor 1\n";
  66.         root = NULL;
  67.         constructTree();
  68.     }
  69.  
  70.     void convertBSTtoDLL() {
  71.         maxMin temp = this->convertBSTtoDLLUtil(this->root);
  72.         Node* tempRoot = temp.min;
  73.         while(tempRoot != NULL) {
  74.             cout << tempRoot->data << "-->";
  75.             tempRoot = tempRoot->right;
  76.  
  77.         }
  78.         cout << "NULL\n";
  79.     }
  80.  
  81.     void constructTree() {
  82.     	/*
  83.          *  BST
  84.          */
  85.         root = new Node(100);
  86.         root->left = new Node(90);
  87.         root->right = new Node(110);
  88.         root->left->left = new Node(80);
  89.         root->left->right = new Node(91);
  90.         root->right->left = new Node(105);
  91.         root->right->right = new Node(120);
  92.         root->left->left->left = new Node(71);
  93.         root->left->left->right = new Node(80);
  94.         root->right->left->right = new Node(107);
  95.     }
  96.  
  97.     ~Tree() {
  98. //        cout << "In destructor\n";
  99.         delete root;
  100.         root = NULL;
  101.     }
  102. };
  103. int main() {
  104. 	Tree t1;
  105.     t1.convertBSTtoDLL();
  106. 	return 0;
  107. }
Runtime error #stdin #stdout 0s 11344KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SDkXY9
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!