Double Linked List and Binary Search Tree transformation in O(n)

This code shows that double linked list and binary tree is essentially the same thing. We can convert one data structure to another in O(n).

#ifndef practice_doubleLinkedList2BST_h
#define practice_doubleLinkedList2BST_h

using namespace std;


struct Node {
    int val;
    Node* left;
    Node* right;
    Node(): val(0), left(nullptr), right(nullptr) {};
    Node(int _val) : val(_val), left(nullptr), right(nullptr) {};
};

Node* helper_doubleLinkedList2BST(Node*& node, int start, int end) {
    if (start > end) return nullptr;
    
    if (start == end) {
        return node; // here we can see the the pointer stops at the end of the linked list.
                     // and the function returns the root of the newly created tree.
    }
    
    int mid = (start + end) / 2;
    
    Node* ptr_mid;
    Node* ptr_left;
    Node* ptr_right;
    
    if (start == mid) { // in this case, there is no left tree
        ptr_left = nullptr;
        ptr_mid = node;
        node = node->right;
        node->left = nullptr;
        ptr_right = helper_doubleLinkedList2BST(node, mid+1, end);
    } else {
        ptr_left = helper_doubleLinkedList2BST(node, start, mid-1);
        // now the node pointes to mid-1
        ptr_mid = node->right;
        node->right = nullptr;
        node = ptr_mid->right;
        node->left = nullptr;
        ptr_right = helper_doubleLinkedList2BST(node, mid+1, end);
    }
    
    ptr_mid->left = ptr_left;
    ptr_mid->right = ptr_right;
    return ptr_mid;
}


Node* doubleLinkedList2BST(Node* node, int length) {
    return helper_doubleLinkedList2BST(node, 0, length-1);
}



pair<Node*, Node*> helper_BST2DoubleLinkedList(Node* node) {
    if (!node) return make_pair(nullptr, nullptr);
    
    pair<Node*, Node*> left = helper_BST2DoubleLinkedList(node->left);
    pair<Node*, Node*> right = helper_BST2DoubleLinkedList(node->right);
    
    left.second->right = node;
    node->left = left.second;
    
    node->right = right.first;
    right.first->left = node;
    
    return make_pair(left.first, right.second);
}

Node* BST2DoubleLinkedList(Node* node) {
    pair<Node*, Node*> result = helper_BST2DoubleLinkedList(node);
    return result.first;
}


#endif