#include <stdexcept>
#include <iostream>

using namespace std;

struct node {
    int val;
    struct node *left;
    struct node *right;
};

void inorder(struct node *root) {
    if (!root) {
        return;
    }
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void traverse_dll(struct node *start, struct node *end) {
    if(!start || !end ||start->left || end->right) {
        throw invalid_argument("Invalid doubly linked list passed");
    }
    struct node *t;
    for(t = start; t != end; t = t->right) {
        cout << t->val << " ";
    }
    cout << t->val << endl;
    for(t = end; t != start; t = t->left) {
        cout << t->val << " ";
    }
    cout << t->val <<endl;
}

void convert(struct node *root, struct node **start, struct node **end) {

    if (!root || !start || !end) {
        // raise an exception if no root is found
        // or if other ptrs are bad
        throw invalid_argument("Invalid pointers passed");
    }

    // convert left sub-tree into doubly linked list
    // start of left dll = left_start, end of dll = left_end
    struct node *left_start, *left_end;
    struct node *left_child = root->left;
    // if there's a left child
    if (left_child) {
        // recursively convert left child
        convert(left_child, &left_start, &left_end);
        // join left_end and root
        left_end->right = root;
        root->left = left_end;
    } else {
        // no left child, make root as left_start
        // Notice that we have no need to populate the left_end
        left_start = root;
    }

    // similarly for right child...
    struct node *right_start, *right_end;
    struct node *right_child = root->right;
    //if there's a right child
    if (right_child) {
        // recurisvely convert right child
        convert(right_child, &right_start, &right_end);
        // join root and right_start
        root->right = right_start;
        right_start->left = root;
    } else {
        // no right child, make root as right_end
        // notice that we have no need to populate
        // right_start in this case
        right_end = root;
    }

    // populate the start and end double pointers with
    // start and end of doubly linked lists...
    *start = left_start;
    *end = right_end;
}

int main() {
    // construct a bst [3 to 17]
    struct node lll = {3, nullptr, nullptr};
    struct node llr = {5, nullptr, nullptr};
    struct node lrl = {7, nullptr, nullptr};
    struct node lrr = {9, nullptr, nullptr};
    struct node rll = {11, nullptr, nullptr};
    struct node rlr = {13, nullptr, nullptr};
    struct node rrl = {15, nullptr, nullptr};
    struct node rrr = {17, nullptr, nullptr};
    struct node ll = {4, &lll, &llr};
    struct node lr = {8, &lrl, &lrr};
    struct node rl = {12, &rll, &rlr};
    struct node rr = {16, &rrl, &rrr};
    struct node l = {6, &ll, &lr};
    struct node r = {14, &rl, &rr};
    struct node root = {10, &l, &r};
    // print inorder
    inorder(&root); cout << endl;
    // convert bst to dll
    struct node *start, *end;
    convert(&root, &start, &end);
    // print doubly linked list
    traverse_dll(start, end);
}