Convert Sorted List To Binary Search Tree

                                            
/**
 * 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) {
        if (head == nullptr) {
            return nullptr;
        }
        if (head->next == nullptr) {
            return new TreeNode(head->val);
        }
        
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = nullptr;
        
        while (fast != nullptr && fast->next != nullptr) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        if (prev != nullptr) {
            prev->next = nullptr;
        }
        
        TreeNode* root = new TreeNode(slow->val);
        
        if (head != slow) {
            root->left = sortedListToBST(head);
        }
        
        root->right = sortedListToBST(slow->next);
        
        return root;
    }
};

                                            
/**
 * 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; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return toBST(head, null);
    }
    
    private 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 node = new TreeNode(slow.val);
        node.left = toBST(head, slow);
        node.right = toBST(slow.next, tail);
        
        return node;
    }
}

                                            
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val

class Solution(object):
    def sortedListToBST(self, head):
        def convertToBST(l, r):
            if l > r:
                return None
            mid = (l + r) // 2
            left = convertToBST(l, mid - 1)
            node = TreeNode(self.head.val)
            node.left = left
            self.head = self.head.next
            node.right = convertToBST(mid + 1, r)
            return node
        
        self.head = head
        size = 0
        current = head
        while current:
            size += 1
            current = current.next
        return convertToBST(0, size - 1)

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* sortedListToBST(struct ListNode* head) {
    if(head == NULL) {
        return NULL;
    }
    
    if(head->next == NULL) {
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = head->val;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    
    struct ListNode* mid = head;
    struct ListNode* prev = NULL;
    struct ListNode* fast = head;
    
    while(fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        prev = mid;
        mid = mid->next;
    }
    
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = mid->val;
    
    if(prev != NULL) {
        prev->next = NULL;
        root->left = sortedListToBST(head);
    } else {
        root->left = NULL;
    }
    
    root->right = sortedListToBST(mid->next);

    return root;
}

                                            
// 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;
    //     }
    // }

public class Solution {
    public TreeNode SortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return new TreeNode(head.val);
        
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        
        while(fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Disconnect left part from mid node
        if(prev != null) prev.next = null;

        TreeNode root = new TreeNode(slow.val);
        root.left = SortedListToBST(head);
        root.right = SortedListToBST(slow.next);
        
        return root;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    const buildBST = (start, end) => {
        if (start > end) {
            return null;
        }
        const mid = Math.floor((start + end) / 2);
        const left = buildBST(start, mid - 1);
        const root = new TreeNode(head.val);
        root.left = left;
        head = head.next;
        root.right = buildBST(mid + 1, end);
        return root;
    }
    
    let currentNode = head;
    let listLength = 0;
    while (currentNode) {
        currentNode = currentNode.next;
        listLength++;
    }
    
    return buildBST(0, listLength - 1);
};

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 */
class Solution {
  
    /**
     * @param ListNode $head
     * @return TreeNode
     */
    function sortedListToBST($head) {
        if(!$head) {
            return null;
        }
        
        $mid = $this->findMid($head);
        
        $node = new TreeNode($mid->val);
        
        if($head === $mid) {
            return $node;
        }
        
        $node->left = $this->sortedListToBST($head);
        $node->right = $this->sortedListToBST($mid->next);
        
        return $node;
    }
    
    function findMid($head) {
        $slow = $head;
        $fast = $head;
        $prev = null;
        
        while($fast && $fast->next) {
            $prev = $slow;
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        
        if($prev) {
            $prev->next = null;
        }
        
        return $slow;
    }
}

                                            
/**
* Definition for singly-linked list.
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/

/**
* Definition for a binary tree node.
* public class TreeNode {
*     public var val: Int
*     public var left: TreeNode?
*     public var right: TreeNode?
*     public init() { self.val = 0; self.left = nil; self.right = nil; }
*     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
*     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
*         self.val = val
*         self.left = left
*         self.right = right
*     }
* }
*/

class Solution {
    func sortedListToBST(_ head: ListNode?) -> TreeNode? {
        guard let head = head else { return nil }
        
        let mid = findMiddle(head)
        let root = TreeNode(mid.val)
        
        if head === mid {
            return root
        }
        
        root.left = sortedListToBST(head)
        root.right = sortedListToBST(mid.next)
        
        return root
    }
    
    func findMiddle(_ head: ListNode?) -> ListNode {
        var slow = head
        var fast = head
        var prev: ListNode?
        
        while let nextFast = fast?.next {
            prev = slow
            slow = slow?.next
            fast = nextFast.next
        }
        
        if let prev = prev {
            prev.next = nil
        }
        
        return slow!
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 *
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */
 
 func sortedListToBST(head *ListNode) *TreeNode {
     if head == nil {
         return nil
     }
     
     if head.Next == nil {
         return &TreeNode{Val: head.Val}
     }
     
     mid := findMiddleElement(head)
     root := &TreeNode{Val: mid.Val}
     
     if head == mid {
         return root
     }
     
     root.Left = sortedListToBST(head)
     root.Right = sortedListToBST(mid.Next)
     
     return root
 }
 
 func findMiddleElement(head *ListNode) *ListNode {
     var prev *ListNode
     slow, fast := head, head
     
     for fast != nil && fast.Next != nil {
         prev = slow
         slow = slow.Next
         fast = fast.Next.Next
     }
     
     if prev != nil {
         prev.Next = nil
     }
     
     return slow
 }

                                            
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
def sorted_list_to_bst(head)
    def find_mid(start, tail)
        slow = fast = start
        while fast != tail && fast.next != tail
            slow = slow.next
            fast = fast.next.next
        end
        slow
    end
    
    def convert_list_to_bst(start, tail)
        return nil if start == tail
        
        mid = find_mid(start, tail)
        node = TreeNode.new(mid.val)
        
        node.left = convert_list_to_bst(start, mid)
        node.right = convert_list_to_bst(mid.next, tail)
        
        node
    end
    
    return convert_list_to_bst(head, nil)
end

To solve this coding challenge, we need to convert a sorted singly linked list to a height-balanced binary search tree (BST).

Explanation

A height-balanced BST ensures that the depth of the two subtrees of every node never differs by more than 1. Given the sorted nature of the list, an in-order traversal of the BST should match the order of elements in the list. This means that the middle element of the list should be the root of the BST, the left half of the list should form the left subtree, and the right half should form the right subtree. To achieve this, we can use a recursive approach:

Count the number of nodes in the list : This helps us determine the size of the BST.
Recursively construct the BST :

Divide the list range into two halves.
The middle element of the current range becomes the root.
Recursively apply the same process to the left half for the left subtree.
Move the list's current head to the next element.
Recursively apply the process to the right half for the right subtree.

Detailed Steps in Pseudocode

Calculate the size of the linked list :

Traverse the linked list and count the number of elements.

Recursive function to construct the BST :

Use two pointers/indices to define the current range of the list.
Find the middle of the current range.
Recursively construct the left subtree.
Assign the current list node's value to the tree node.
Move to the next list node.
Recursively construct the right subtree.

Initialize :

Set the head of the linked list.
Start the recursive function with the full range of the list.

Pseudocode

                                            
# Define the ListNode and TreeNode as basic data structures
class ListNode:
def __init__(self, val, 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

# Main function to convert sorted list to BST
function sortedListToBST(head):
# Helper function to count the number of nodes in the list
function countNodes(node):
count = 0
while node != null:
count += 1
node = node.next
return count

# Helper function to recursively convert list to BST
function convertToBST(left, right):
if left > right:
return null
mid = (left + right) // 2

# Recursively form the left subtree
leftChild = convertToBST(left, mid - 1)

# Node to be the root
root = TreeNode(head.val)
root.left = leftChild

# Move to the next list node
head = head.next

# Recursively form the right subtree
root.right = convertToBST(mid + 1, right)

return root

size = countNodes(head)  # Calculate the size of the list
return convertToBST(0, size - 1)  # Form the BST

Step-by-Step Explanation of the Pseudocode:

Initialization of ListNode and TreeNode Classes :

ListNode : Represents a node in the singly linked list with a value and a pointer to the next node.
TreeNode : Represents a node in the binary search tree with a value, a left child, and a right child.

Main Function
sortedListToBST(head)

:

countNodes(node)

function : Counts the total number of nodes in the linked list by traversing from the head to the end.
convertToBST(left, right)

function : This recursive function constructs the BST:

Base Case : If the left index exceeds the right index, return
null

. This indicates that there is no more node to include in the current subtree.
Find the middle point : Calculate the middle index of the current range to decide the root of the current subtree.
Recursive Construction of Left Subtree : Call
convertToBST

for the left half of the current range.
Root Node Construction : Create a new
TreeNode

with the current value of
head

, set the left child to the result of the left subtree construction, and move the head to the next node.
Recursive Construction of Right Subtree : Call
convertToBST

for the right half of the current range and set the right child to the result.

Calculate List Size and Begin Conversion : Determine the size of the list, then call
convertToBST

with the full range of indices.

Using these detailed steps and thorough comments in the pseudocode, we can carefully convert the sorted linked list into a height-balanced binary search tree.