# Sorted List to binary search tree O(nlogn) time complexity

while(step2->next != NULL && step2->next->next != NULL){
step1 = step1->next;
step2 = step2->next->next;
}
TreeNode *root  = new TreeNode(step1->next->val);
delete step1->next;
step1->next = NULL;
return root;
}

• Do bottom up approach and construct the tree from the leaves rather than doing top down approach and constructing tree from root to get o(n) time complexity.

STEP 1: Take left n/2 nodes and recursively construct the left sub tree.

STEP 2: After left sub tree is constructed, we allocate memory for root and link the left sub tree with root.

STEP 3: Finally, we recursively construct the right sub tree and link it with root.

class Solution {
public:
ListNode *list;
int lengthOfList(ListNode *node){
int length = 0;
while (node) {
length++;
node = node->next;
}
return length;
}
TreeNode *populateTree(int n){
if (n == 0)
return NULL;
TreeNode *treenode = new TreeNode(0);
treenode->left = populateTree(n / 2);
treenode->val = list->val;
list = list->next;
treenode->right = populateTree(n - n / 2 - 1);
return treenode;
}