|
Given a singly linked list where elements are sorted in ascending order convert it to a height-balanced binary search tree.
Example:
Input:
Linked List: 1->2->3->4->5->6->7
Output:
4
/ \
2 6
/ \ / \
1 3 5 7 ApproachTo achieve a balanced BST from the sorted linked list one can use the properties of the sorted list and recursively build the tree. The middle element of the list will be the root of the BST. The left half of the list will form the left subtree and the right half will form the right subtree.
Steps:- Find the middle of the linked list: This will be the root of the BST.
- Recursively apply the same process: For the left half and right half of the list.
- Construct the BST: Using the nodes as they are recursively divided.
Example : To demonstrate creating sorted linked list to a Balanced BST using JavaScript.
JavaScript
class list_Node {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class tree_Node {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
// Helper function to find the
// middle node of the linked list
function Middle_value(start) {
let slow = start;
let fast = start;
let prev = null;
while (fast !== null && fast.next !== null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if (prev !== null) {
prev.next = null;
// Split the linked list into the two halves
}
return slow;
}
// Main function to the convert sorted
// linked list to the balanced BST
function sortedNoToBST(head) {
if (head === null) {
return null;
}
// Find the middle of the list
let mid = Middle_value(head);
// The middle element becomes the root
let root = new tree_Node(mid.val);
// Base case: If there's only one element return it as root
if (head === mid) {
return root;
}
// Recursively build the left and right subtrees
root.left = sortedNoToBST(head);
root.right = sortedNoToBST(mid.next);
return root;
}
// Helper function to print the tree
// in-order for the verification
function inOrderTraversal(root) {
if (root === null) {
return;
}
inOrderTraversal(root.left);
console.log(root.val);
inOrderTraversal(root.right);
}
let head = new list_Node(-10);
head.next = new list_Node(-3);
head.next.next = new list_Node(0);
head.next.next.next = new list_Node(5);
head.next.next.next.next = new list_Node(9);
let bstRoot = sortedNoToBST(head);
console.log("In-order traversal of the BST:");
inOrderTraversal(bstRoot);
OutputIn-order traversal of the BST:
-10
-3
0
5
9
Time Complexity: O(nlogn)
Auxiliary Space: O(logn)
|
