Convert Binary Search Tree to Sorted Doubly Linked List - CPP Solution

1. Introduction

This blog post explores the process of converting a Binary Search Tree (BST) into a sorted doubly linked list. The challenge lies in maintaining the order of the elements and efficiently modifying the pointers to form the doubly linked list.

Problem

Given the root of a Binary Search Tree (BST), convert it into a sorted doubly linked list. The elements of the doubly linked list should follow the same order as a in-order traversal of the BST. Additionally, it's required to make the conversion in place without using extra space.

2. Solution Steps

1. Perform an in-order traversal of the BST.

2. During traversal, rewire the nodes to form a doubly linked list by modifying their left and right pointers.

3. Ensure that the head of the doubly linked list points to the smallest element, and the list is sorted in ascending order.

3. Code Program

#include <iostream>
using namespace std;

// TreeNode structure for BST
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Node structure for Doubly Linked List
struct Node {
    int val;
    Node *prev, *next;
    Node(int x) : val(x), prev(nullptr), next(nullptr) {}
};

// Function to convert BST to sorted doubly linked list
Node* convertBSTtoSortedDLL(TreeNode* root) {
    if (!root) return nullptr;
    static Node* prev = nullptr;
    Node* head = convertBSTtoSortedDLL(root->left);
    Node* current = new Node(root->val);
    current->prev = prev;
    if (prev) prev->next = current;
    prev = current;
    convertBSTtoSortedDLL(root->right);
    return head ? head : current;
}

// Function to print the doubly linked list
void printDoublyLinkedList(Node* head) {
    Node* current = head;
    while (current) {
        cout << current->val << " <-> ";
        current = current->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a BST
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);

    Node* head = convertBSTtoSortedDLL(root);
    printDoublyLinkedList(head); // Expected output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> nullptr
    return 0;
}

Output:

1 <-> 2 <-> 3 <-> 4 <-> 5 <-> nullptr

Explanation:

The convertBSTtoSortedDLL function traverses the BST in an in-order manner and constructs the sorted doubly linked list. 

During the traversal, it creates new nodes for the linked list, setting their prev and next pointers appropriately to form the doubly linked list. 

The function maintains a static pointer prev to keep track of the previously visited node, enabling the linking of the current node with its predecessor. 

The in-order traversal ensures that the nodes are visited in ascending order, creating a sorted doubly linked list.