Solution For Convert Sorted List To Binary Search Tree

Problem statement:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:
To solve this problem, we can follow the below approach:
1. First, we need to find the middle element of the linked list.
2. Then we can create a TreeNode with the middle element.
3. We can then recursively create the left and right subtrees using the nodes before and after the middle element in the linked list.
4. We can repeat the above steps until the entire list is used up or we have no more nodes to create subtrees.

Below is the code implementation in Python:

“`
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if not head:
return None
if not head.next:
return TreeNode(head.val)

    # find middle node using slow and fast pointer
    slow, fast = head, head.next.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # create a TreeNode with the middle value
    root = TreeNode(slow.next.val)

    # recursively create left and right subtrees
    rightHead = slow.next.next
    slow.next = None
    root.left = self.sortedListToBST(head)
    root.right = self.sortedListToBST(rightHead)

    return root

“`

The time complexity of the above code is O(n log n), where n is the number of nodes in the linked list. This is because we need to find the middle element using the slow and fast pointer, which takes O(n) time. And then for each subtree, we need to recursively process half the number of nodes, which also takes O(n) time. Hence the overall time complexity is O(n log n).

The space complexity of the above code is O(log n), which is the space required for the recursion stack. This is because for each level of the recursion tree, we only need to store the root of the subtree.

Test Cases:
Let’s consider a few test cases to validate our solution:

Example 1:
Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the following BST:
0
/ \
-3 9
/ /
-10 5

Example 2:
Input: head = [1,3] Output: [3,1] Explanation: One possible answer is [3,1], which represents the following BST:
3
\
1

Example 3:
Input: head = [] Output: []

In conclusion, we have successfully solved the Convert Sorted List to Binary Search Tree problem on Leetcode using a recursive approach.

Step by Step Implementation For Convert Sorted List To Binary Search Tree

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null) return null;
        return toBST(head,null);
    }
    public TreeNode toBST(ListNode head, ListNode tail){
        ListNode slow = head;
        ListNode fast = head;
        if(head==tail) return null;
        
        while(fast!=tail&&fast.next!=tail){
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode thead = new TreeNode(slow.val);
        thead.left = toBST(head,slow);
        thead.right = toBST(slow.next,tail);
        return thead;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # if the head is empty, return None
        if not head:
            return None
        
        # if the head is the only element in the list, return the head
        if not head.next:
            return TreeNode(head.val)
        
        # find the middle element of the list
        slow = head
        fast = head.next.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # split the list into two halves
        mid = slow.next
        slow.next = None
        
        # create the root node with the value of the middle element
        root = TreeNode(mid.val)
        
        # recursively call the function to create the left subtree
        root.left = self.sortedListToBST(head)
        
        # recursively call the function to create the right subtree
        root.right = self.sortedListToBST(mid.next)
        
        return root

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    //if the list is empty, return null
    if(head === null) {
        return null;
    }
    
    //if the list only has one node, return that node as the root
    if(head.next === null) {
        return new TreeNode(head.val);
    }
    
    //find the middle node of the list
    let slow = head;
    let fast = head;
    let prev = null;
    
    while(fast !== null && fast.next !== null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    //set the middle node as the root
    let root = new TreeNode(slow.val);
    
    //set the left child as the list before the middle node
    root.left = sortedListToBST(head);
    
    //set the right child as the list after the middle node
    root.right = sortedListToBST(slow.next);
    
    return root;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        
        // Base case
        if(head == NULL){
            return NULL;
        }
        
        // Find the middle element for the list
        ListNode *mid = findMiddle(head);
        
        // Make the middle element the root of the tree
        TreeNode *root = new TreeNode(mid->val);
        
        // Base case when there is only one element in the linked list
        if(head == mid){
            return root;
        }
        
        // Recursively form balanced BSTs using the left and right halves of the original list.
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(mid->next);
        
        return root;
    }
    
    ListNode* findMiddle(ListNode *head){
        
        // The pointer used to disconnect the left half of the linked list from the mid node.
        ListNode *prevPtr = NULL;
        // Slow pointer used to form the left half of the linked list.
        ListNode *slowPtr = head;
        // Fast pointer used to form the right half of the linked list.
        ListNode *fastPtr = head;
        
        // Iterate until fastPr doesn't reach the end of the linked list.
        while(fastPtr != NULL && fastPtr->next != NULL){
            fastPtr = fastPtr->next->next;
            prevPtr = slowPtr;
            slowPtr = slowPtr->next;
        }
        
        // Handling the case when slowPtr was equal to head.
        if(prevPtr != NULL){
            prevPtr->next = NULL;
        }
        
        return slowPtr;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedListToBST(ListNode head) {
        //edge case - if head is null, return null
        if(head == null){
            return null;
        }
        
        //if head is not null, find the middle of the list
        ListNode middle = FindMiddle(head);
        
        //create a new tree node with the value of the middle node
        TreeNode node = new TreeNode(middle.val);
        
        //if the middle node is the same as the head node, set the head's next node to be the left child of the tree node, and return the tree node
        if(middle == head){
            node.left = null;
        }
        
        //if the middle node is not the same as the head node, set the head node to be the left child of the tree node
        else{
            node.left = SortedListToBST(head);
        }
        
        //set the middle node's next node to be the right child of the tree node, and return the tree node
        node.right = SortedListToBST(middle.next);
        
        return node;
    }
    
    //helper function to find the middle node of a list
    public ListNode FindMiddle(ListNode head){
        //edge case - if head is null, return null
        if(head == null){
            return null;
        }
        
        //slow and fast pointers to find the middle of the list
        ListNode slow = head;
        ListNode fast = head;
        
        //while loop to find the middle of the list
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        //return the middle node
        return slow;
    }
}