Monday, February 17, 2014

Convert Sorted List to Binary Search Tree (Java)

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

Solution:
Provide two solutions below.  One is relatively simple to come out which just convert the LinkedList to
 array then Convert the array to BST. But this solution may not be the one Interviewer wants.

The second one  performs the conversion in place, apply the feature of linked list  we can build the tree
from  bottom to up. Meanwhile use start and end two value to indicate the bounds