Given a sorted Linkedlist, convert it into complete Binary Search Tree.

Example:

Input:
1 -> 3 -> 5 -> 7 -> 9

Output : 
      7
	 /\
    3  9
   /\
  1  5

I was not able to solve it completely. we discussed like representation of nodes (i, 2i + 1, 2i+2), number of nodes in last level based on linkedlist size. Then we implemented building complete binary search tree based on tree structure representation given below. Then I was asked to use this method to convert LL to Arrays.

root - i
left - 2i + 1
right - 2i + 2

     1
     /\
    2  3
    /\
   4  5

Note : A complete binary search tree is a binary search tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.