<p>I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child.</p>

<p>By induction you can prove that the resulting tree is balanced since you are building trees of the same size at each side (+/- 1 node). Also is easy to prove that the result is a binary search tree, by construction.</p>

<p>With respect to the complexity, every node in the recursive execution tree takes constant time. Since you have a number of nodes proportional to the number of elements in your input, then the algorithm is O(n).</p>

CC BY-SA 3.0
2014-06-11T00:11:27.557Z
Agreed. The complexity is linear and the space is logarithmic.
J.y B.y
CC BY-SA 3.0
2014-06-07T16:53:55.710Z
2014-06-07T16:53:55.710Z
ees_cu
<p>Although this is not exactly the question you asked, you can also build balanced trees from ordered data in an online manner.  That is to say, you could walk your array from left-to-right building up partial results, and if some asked you to stop after <em>k</em> items you could finish building the tree in log <em>k</em> time (with the total time being O(<em>k</em>), and the extra storage required O(log <em>k</em>).</p>

<p>To state this another way, you could read the data from a pipe and create the tree (via auxilliary structures) without first putting it all in an array first (thereby avoiding the O(<em>n</em>) storage required for the array).  Algorithms to do this for red-black trees can be found hidden in the SML NJ library implementation of red-black sets.  The theoretical underpinnings can be found in Okasaki's <em>Purely Functional Data Structures</em>.</p>

<p>I have found a similar algorithm for AVL (height-balanced) trees, but I have not (yet) published it, as I don't know whether it is part of the published literature for AVL trees.</p>

CC BY-SA 3.0
2014-06-12T00:29:05.480Z
2014-06-12T00:29:05.480Z
David C
<p>I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time?</p>

<p>I am facing a problem where I have about 8 million elements in a file that need to be loaded into a BST so O(n) would be vastly preferable to O(n log n) if it's possible.</p>

CC BY-SA 3.0
2014-06-12T00:49:45.017Z
This is not a research-level question in theoretical computer science. https://cstheory.stackexchange.com/help/on-topic
jbapple
CC BY-SA 3.0
2014-06-12T01:08:59.033Z
Ya this is a better question for stack exchange
Jake
<tree><binary-trees>
Pre order traversal of an array
David Carpenter
# Pre order traversal of an array

(Asked by: username_0 on 2014-06-07)

I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time?

I am facing a problem where I have about 8 million elements in a file that need to be loaded into a BST so O(n) would be vastly preferable to O(n log n) if it's possible.

**Tags:** tree, binary-trees
> **Comments:**
> **username_1**: This is not a research-level question in theoretical computer science. https://cstheory.stackexchange.com/help/on-topic  
> **username_2**: Ya this is a better question for stack exchange  

---

## 2 answers

### Answer by username_3 on 2014-06-07. Score: 3

I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child.

By induction you can prove that the resulting tree is balanced since you are building trees of the same size at each side (+/- 1 node). Also is easy to prove that the result is a binary search tree, by construction.

With respect to the complexity, every node in the recursive execution tree takes constant time. Since you have a number of nodes proportional to the number of elements in your input, then the algorithm is O(n).

> **Comments:**
> **username_4**: Agreed. The complexity is linear and the space is logarithmic.  

---

### Answer by username_5 on 2014-06-12. Score: 2

Although this is not exactly the question you asked, you can also build balanced trees from ordered data in an online manner. That is to say, you could walk your array from left-to-right building up partial results, and if some asked you to stop after *k* items you could finish building the tree in log *k* time (with the total time being O(*k*), and the extra storage required O(log *k*).

To state this another way, you could read the data from a pipe and create the tree (via auxilliary structures) without first putting it all in an array first (thereby avoiding the O(*n*) storage required for the array). Algorithms to do this for red-black trees can be found hidden in the SML NJ library implementation of red-black sets. The theoretical underpinnings can be found in Okasaki's *Purely Functional Data Structures*.

I have found a similar algorithm for AVL (height-balanced) trees, but I have not (yet) published it, as I don't know whether it is part of the published literature for AVL trees.


---

