Convert Sorted Listto Binary Search Tree Algorithm
The Convert Sorted List to Binary Search Tree Algorithm is a technique used to transform a sorted linked list into a balanced binary search tree (BST). This algorithm is particularly useful when working with large datasets, as it ensures that the resulting BST has minimal height, which optimizes search operations. The premise of the algorithm is to find the middle element of the sorted list and use it as the root of the BST. This process is then recursively applied to the left and right halves of the list, ensuring that the resultant tree is balanced.
To implement the algorithm, first, the length of the linked list is calculated. Next, a helper function is defined to recursively build the BST. This function takes two parameters - the start and end indices of the linked list segment. At each step, the middle element of the segment is determined and a new tree node is created with its value. The helper function is then recursively called for the left and right halves of the segment, with the resulting tree nodes being assigned as left and right children of the current node. The base case for the recursion is when the start index is greater than or equal to the end index, at which point a null pointer is returned. Finally, the algorithm returns the root node of the constructed BST, which can then be traversed or manipulated as needed.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
if (head == NULL) {
return NULL;
}
if (head->next == NULL) {
return new TreeNode(head->val);
}
ListNode prevhead(0);
prevhead.next = head;
ListNode* prev = &prevhead;
ListNode* one = head;
ListNode* two = head;
while (two && two->next) {
prev = prev->next;
one = one->next;
two = two->next->next;
}
TreeNode* root = new TreeNode(one->val);
ListNode* temp = one->next;
prev->next = NULL;
one->next = NULL;
root->left = sortedListToBST(head);
root->right = sortedListToBST(temp);
return root;
}
};
