Convert Sorted List to Binary Search Tree - CPP Solution

1. Introduction

This blog post delves into a unique problem that bridges linked lists and binary search trees (BSTs): converting a sorted linked list into a height-balanced BST. The challenge lies in maintaining the sorted order and ensuring that the resulting tree is height-balanced.

Problem

Given the head of a singly linked list where elements are sorted in ascending order, the task is to convert it into a height-balanced binary search tree.

2. Solution Steps

1. Find the middle element of the linked list, which will be the root of the BST.

2. Recursively repeat the process for the left and right halves of the list to build the left and right subtrees.

3. Ensure that the tree remains height-balanced by appropriately choosing the middle element at each level of recursion.

4. Return the root of the constructed BST.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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

// Function to find the middle element of the list
ListNode* findMiddle(ListNode* head) {
    ListNode *prevPtr = nullptr, *slowPtr = head, *fastPtr = head;
    while (fastPtr && fastPtr->next) {
        prevPtr = slowPtr;
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;
    }

    // Disconnect the left half from the middle
    if (prevPtr) prevPtr->next = nullptr;
    return slowPtr;
}

// Function to convert sorted list to BST
TreeNode* sortedListToBST(ListNode* head) {
    if (!head) return nullptr;
    if (!head->next) return new TreeNode(head->val);

    ListNode *mid = findMiddle(head);
    TreeNode *root = new TreeNode(mid->val);
    root->left = sortedListToBST(head);
    root->right = sortedListToBST(mid->next);

    return root;
}

// Function to perform in-order traversal of the BST
void inorderTraversal(TreeNode* root) {
    if (!root) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    // Creating a sorted linked list
    ListNode* head = new ListNode(-10);
    head->next = new ListNode(-3);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(5);
    head->next->next->next->next = new ListNode(9);

    TreeNode* root = sortedListToBST(head);
    cout << "In-order Traversal of the constructed BST: ";
    inorderTraversal(root); // Expected output: -10 -3 0 5 9
    return 0;
}

Output:

In-order Traversal of the constructed BST: -10 -3 0 5 9

Explanation:

The sortedListToBST function converts a sorted linked list into a height-balanced BST. It first finds the middle element of the list to use as the root of the BST. Then, it recursively constructs the left and right subtrees by repeating the process for the left and right halves of the list. The findMiddle function is used to get the middle element and split the list. This approach ensures that the resulting BST is height-balanced and maintains the order of elements. The inorderTraversal function is used to verify the correctness of the BST construction.