Sorted List to Balanced Binary Search Tree

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

We can solve this problem using bottom up approach with recursion. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.  Lets define the node structure for Binary Search Tree Node as follows

Below is the java code for converting a singly linked list to a balanced BST. The algorithm requires the list’s length to be passed in as the function’s parameters. The list’s length could be found in O(N) time by traversing the entire list’s once. The recursive calls traverse the list and create tree’s nodes by the list’s order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).