Convert doubly linked list to
balanced BST in O(n)
it were a sorted array, then converting to BST is easy.
make middle of array as root and recurse for left and right array
recursive call returns left and right subtrees which should be
current node’s children.
a linked list, this is little difficult because we have to move to
middle of current sublist, which takes n/2, n/4 and so on steps in
each recursion. So a naive approach would become O(nlogn) approach.
make it O(n), we use recursion again, so that left subtree constructs
first exhausting the first half of the list. When left recursion
ends, the list is moved to the middle (because its a global variable)
and we can use it to create a new root.