Create Balanced Binary Search Tree from Sorted linked list

Question

What's the best way to create a balanced binary search tree from a sorted singly linked list?

Answer 1

How about creating nodes bottom-up?

This solution's time complexity is O(N). Detailed explanation in my blog post:

http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

Two traversal of the linked list is all we need. First traversal to get the length of the list (which is then passed in as the parameter n into the function), then create nodes by the list's order.

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {   if (start > end) return NULL;   // same as (start+end)/2, avoids overflow   int mid = start + (end - start) / 2;   BinaryTree *leftChild = sortedListToBST(list, start, mid-1);   BinaryTree *parent = new BinaryTree(list->data);   parent->left = leftChild;   list = list->next;   parent->right = sortedListToBST(list, mid+1, end);   return parent; }  BinaryTree* sortedListToBST(ListNode *head, int n) {   return sortedListToBST(head, 0, n-1); } 

Answer 2

You can't do better than linear time, since you have to at least read all the elements of the list, so you might as well copy the list into an array (linear time) and then construct the tree efficiently in the usual way, i.e. if you had the list [9,12,18,23,24,51,84], then you'd start by making 23 the root, with children 12 and 51, then 9 and 18 become children of 12, and 24 and 84 become children of 51. Overall, should be O(n) if you do it right.

The actual algorithm, for what it's worth, is "take the middle element of the list as the root, and recursively build BSTs for the sub-lists to the left and right of the middle element and attach them below the root".