/**
 * Use in-order traversal to generate BST from left bottom to top, then to right bottom.
 * Keep a pointer to trac of a node to go over each node in list, after left children 
 * are done, the pointer currently pointer to parent node, then go next to genereate right
 * children.
 *
 * For this solution, the time complexity would be 0(n), and space complexity would be O(log n);
 *
 * If solving as array, i.e. everytime find the mid node in partial list, then the time complexity
 * would be O(n log n) but space complexity may be O(1)
 */

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode *sortedListToBST(ListNode* &ln, int len) {
    if (len <= 0) return NULL;

    TreeNode *lChild = sortedListToBST(ln, len/2);
    TreeNode *tn = new TreeNode(ln->val);
    tn->left = lChild;
    ln = ln->next;
    tn->right = sortedListToBST(ln, len-1-len/2);

    return tn;
}

TreeNode *sortedListToBST(ListNode *head) {
    ListNode *ln = head;
    // calculate the length of linked list
    int len = 0;
    while(ln != NULL) {
        ln = ln->next;
        ++len;
    }

    ln = head;
    sortedListToBST(ln, len);
}