Untitled

/**
 * 
 * Given two binary search trees, merge them into one Doubly Linked List.
 * First implement ONE BST to one sorted doubly linked list.
 *      1. Print In Order
 *      2. linkedlist printer front and back traversal
 *      3. insert in tree
 *      4. implement BST to LinkedList
 */

#include <iostream>
#include <queue>
using namespace std;

struct treenode {
    int val;
    treenode* left;
    treenode* right;
    treenode(int x) : val(x), left(nullptr), right(nullptr) {};
};

treenode* InsertBST(treenode* root, int val) {
    if (root == nullptr) {
        treenode* newNode = new treenode(val);
        return newNode;
    }

    if (root->val > val) { // left subtree
        root->left = InsertBST(root->left, val);
    } else { // right subtree
        root->right = InsertBST(root->right, val);
    }

    return root;
} 

void destroy(treenode* root) {
    if (root == nullptr) return;
    destroy(root->left);
    destroy(root->right);
    free(root);
}

void PrintInOrderHelper(treenode* root){
    if(root == nullptr) return;
    PrintInOrderHelper(root->left);
    cout << root->val << " ";
    PrintInOrderHelper(root->right);
}

void PrintInOrder(treenode* root) {
    cout << "Printing In Order: [ ";
    PrintInOrderHelper(root);
    cout << "]" << endl;
}

int PrintBSTLevelOrder(treenode* root) {
    /** prints the BST in level order and returns the height of the tree */
    int height = 0;
    int currLevelSize = 0;
    if (root == nullptr) return height;
 
    cout << "Printing In Level: [ ";
    queue<treenode*> tree_q;
    tree_q.push(root);
    while(!tree_q.empty()) {
        height += 1;
        currLevelSize = tree_q.size();

        for (int i = 0; i < currLevelSize; i++) {
            treenode* curr = tree_q.front();
            tree_q.pop();
            cout << curr->val << " ";
            if (curr->left != nullptr) tree_q.push(curr->left);
            if (curr->right != nullptr) tree_q.push(curr->right);
        }
    }
    cout << "]" << endl;

    return height;
    
}

void PrintLinkedListFromHead(treenode* head) {
    cout << "*Inorder LL Print: ";
    treenode* temp = head;
    cout << "[ ";
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->right;
    }

    cout << "]" << endl;
}

void PrintLinkedListFromTail(treenode* tail) {
    cout << "*Reverse LL Print: ";
    treenode* temp = tail;
    cout << "[ ";
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->left;
    }

    cout << "]" << endl;
}

void BSTtoDoublyLinkedList(treenode* root, treenode* &head, treenode* &tail) {
    if (root == nullptr) return;
    BSTtoDoublyLinkedList(root->left, head, tail);
    /* 
        Do work here to convert current inorder node to 
    */
    if (head == nullptr) {
        head = root;
    } else {
        tail->right = root;
        root->left = tail;
    }

    tail = root;
    BSTtoDoublyLinkedList(root->right, head, tail);
}

void TwoBSTtoDoublyLinkedList(treenode* root1, treenode* root2, treenode* head, treenode* tail) {
    /**
     * BRUTE FORCE way to do this is to insert all nodes of root2 into root1
     *      ISSUES is that it can result in an imbalanced tree
     *          We also make A LOT of redundant, recursive calls here
     *  
     * SOLN: one run by using 3 unique basecases
     *  1. when root1 and root2 == nullptr
     *  2. when root1 is NOT    null AND [either root2 is     null  or root1.val comes before root2.val]
     *  2. when root1 is either null  OR [       root2 is NOT null AND root1.val comes  after root2.val]
     */

    if (root1 == nullptr && root2 == nullptr) return;
    if (root1 != nullptr && (root2 == nullptr || root1->val < root2->val)) {
        // set root1 as the next element in tail    
        TwoBSTtoDoublyLinkedList(root1->left, root2, head, tail);
        if (head == nullptr) head = tail = root1;
        else {
            tail->right = root1;
            root1->left = tail;
            tail = root1;
        }

        TwoBSTtoDoublyLinkedList(root1->right, root2, head, tail);
    } else { 
        // either root1 value is NULL
        //     OR root2 value is NOT null AND root1.val is greater than root2.val
        // In either way we need to set root2 as the next elemenet in the tail
        TwoBSTtoDoublyLinkedList(root1, root2->left, head, tail);
        if (head == nullptr) head = tail = root2;
        else {
            tail->right = root2;
            root2->left = tail;
            tail = root2;
        }
        
        TwoBSTtoDoublyLinkedList(root1, root2->right, head, tail);
    }

}

int main() {
    treenode* root = nullptr;
    root = InsertBST(root, 3);
    root = InsertBST(root, 1);
    root = InsertBST(root, 7);
    root = InsertBST(root, 5);
    root = InsertBST(root, 10);

    treenode* root2 = nullptr;
    root2 = InsertBST(root2, 6);
    root2 = InsertBST(root2, 2);
    root2 = InsertBST(root2, 4);
    root2 = InsertBST(root2, 0);
    root2 = InsertBST(root2, 9);
    root2 = InsertBST(root2, 8);
    root2 = InsertBST(root2, 11);


    /* Printing in order */    
    PrintInOrder(root);
    /* Printing in level */
    PrintBSTLevelOrder(root);

    /* Printing in order */    
    PrintInOrder(root2);
    /* Printing in level */
    PrintBSTLevelOrder(root2);



    treenode* head = nullptr;
    treenode* tail = nullptr;
    TwoBSTtoDoublyLinkedList(root, root2, head, tail);

    // /* print linked list forward*/
    // PrintLinkedListFromHead(head);
    // /* print linked list backwards*/
    // PrintLinkedListFromTail(tail);


}