How to construct Binary Search Tree bottom-up

Question

Given a sorted array, it is very easy to visualize a BST from it in a top-down manner. For example, if the array is [1,2,3,4,5,6,7], we can see that the root will be the middle element, that is 4. To its left there will be a subtree whose root is the middle of the array slice to the left of 4, that is 2. In the same way it will be similar in the right also.

How can we do this visualization for the bottom-up approach to constructing the BST? Basically I am trying to understand the algorithm to construct a BST from a sorted linked list, which takes O(N) in bottom-up manner, and O(Nlog N) in topdown manner. So I need to understand how it builds bottom-up.

Answer 1

Consider: http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}

Let's write out some of the recursive calls:

0 1 2 3 4 5 6 7 8 -> sortedListToBST(list, 0, 3) [A]
0 1 2 3           -> sortedListToBST(list, 0, 0) [B]
0                 -> sortedListToBST(list, 0, -1) [C]
*                 -> NULL [D]

[D] will return NULL.

Now, in [C], we will have leftChild = NULL and parent = 0 (first node in the list). The parent's left child will be NULL, and the list progresses. [C] will then call sortedListToBst(1, 0), which will return NULL, so the right child of parent will also be NULL. Your tree so far looks like this:

        0
     /     \
  null     null

Now, this will be returned to the left call in [B], so leftChild = 0 = the above in [B]. The parent in [B] will set itself to 1 (the second node in the list, note that we advanced the list head in a previous call - the list is global / passed by reference). Its left child will be set to what you compute in the previous step (the above tree). Your tree now looks like this:

        1
      /
     0
  /     \
null   null

The list is advanced again, pointing to 2. A recursive call sortedListToBST(list, 2, 3) will be made from [B], which will trigger multiple recursive calls.

It's a lot to write / explain, but hopefully this sets you on the right track. It should be easier to follow on paper.