Build BST from sorted array and Linked List

Q:Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Q:Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

It’s more efficient to build a sorted array fist and use that array to build the BST. This require O(n) space and O(n) time.

List Flattening and List Unflattening

Q:PIE P:53

These function haven’t been tested yet.
List Flattening:

```void flattenList(Node head,Node tail){
Node childTail;
//childTail is used for finding the tail of the child

/**Traverse through the list **/
while(curr.next!=null){
/**Find child**/
if(curr.child!=null){
/**After found a child,
//1)link the child to the tail
//2)find the tail of the child's list
//3)update tail**/

/**1)link the child to the tail**/
tail.next=curr.child;
curr.child.prev=tail;

/**2)find the tail of the child's list**/
childTail=curr.child;
while(childTail.next!=null){
childTail=childTail.next;
}

/**3)update tail**/
tail=childTail;
}
curr=curr.next;
}
}
```

List Unflatterning:

```void unflattenList(Node head, Node tail){

/**Traverse through the list 1st time & breaking the prev link of child;
//the breaking prev link is a mark of a child**/
while(curr.next!=null){
/**Find a child**/
if(curr.child!=null){
curr.child.prev=null;
}
curr=curr.next;
}

/**Traverse through the list 1st time & breaking the next link which links to a child**/
while(curr.next!=null){
/**Find a child**/
if(curr.prev==null){
prevNode.next=null;
}
prevNode=curr;
curr=curr.next;
}

/**Update the tail**/
while(curr.next!=null){
curr=curr.next;
}
tail=curr;
}
```

List Unflattening, using recursion.
/*
* Algorithm:
* Explore path:
* While not at the end
* If current node has a child
* Separate the child from its previous node
* Explore path beginning with the child
* Go onto the next node
*/

```

/**Update the tail**/
while(curr.next!=null){
curr=curr.next;
}
tail=curr;
}

while(curr.next!=null){
next=curr.next;
/**Find a child**/
if(curr.child!=null){
Node child = curr.child;