# How to Convert Sorted List to Binary Search Tree

Written by:

Stacktips,  7 min read,  updated on February 17, 2024

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced Binary Search Tree (BST).

To convert a sorted singly linked list to a height-balanced Binary Search Tree (BST), we will use the recursive approach. The key idea is to find the middle element of the linked list, make it the root of the BST, and then recursively do the same for the left and right halves of the linked list.

#### Java implementation

class ListNode {
int val;
ListNode next;

ListNode(int val) {
this.val = val;
}
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int val) {
this.val = val;
}
}

public class SortedListToBST {
return null;
}

}

private TreeNode sortedListToBST(ListNode head, ListNode tail) {
return null;
}

// Using the slow and fast pointers to find the middle element
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}

// The root node with the middle element
TreeNode root = new TreeNode(slow.val);

// Recursively build the left and right subtrees
root.right = sortedListToBST(slow.next, tail);

return root;
}

public static void main(String[] args) {
// Example usage
SortedListToBST converter = new SortedListToBST();

// Create a sorted linked list

// Convert the linked list to a balanced BST

System.out.println("Inorder traversal of the resulted BST:");
inorderTraversalBST(result);
}

private static void inorderTraversalBST(TreeNode result) {
if (result != null) {
inorderTraversalBST(result.left);
System.out.print(result.val + " ");
inorderTraversalBST(result.right);
}
}
}
Output
Inorder traversal of the resulted BST:
-10 -3 0 5 9

### Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(log n) (call stack) + O(n) (additional space)

#### Time Complexity

• The time complexity is mainly determined by the recursive method to convert the sorted linked list to a balanced BST. In each recursive call, we perform constant-time operations, such as creating nodes and updating pointers.
• The number of recursive calls is proportional to the number of nodes in the linked list.
• Therefore, the time complexity is O(n), where n is the number of nodes in the linked list.

#### Space Complexity

• The space complexity is influenced by the space required for the recursive calls on the call stack.
• In the worst case, the maximum depth of the recursion is equal to the height of the balanced BST.
• The height of a balanced BST constructed from a sorted linked list is approximately log₂(n), where n is the number of nodes.
• Therefore, the space complexity of the call stack is O(log n).
• There is additional space required for the linked list nodes and the BST nodes. However, these contribute at most O(n) to the space complexity.

Java Collection APIs

The Collections framework in Java defines numerous different data structures in which you can store, group, and retrieve objects.