[Leetcode] Convert Sorted Array or Singly Linked List to Binary Search Tree

Problem

Given an array where elements are sorted in ascending order, or a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Algorithm

Select the middle element as the root. Recursively build the subtrees and append them to the root.
If given a sorted linked list, we cannot access the root element in O(1), but in O(n). If we use the above algorithm, the running time is O(n * Log(n)).

A bottom up O(n) solution is shown in the code below.

Code