A fast algorithm for constructing balanced binary search trees

Pavel S. Ruzankin

We suggest a new non-recursive algorithm for constructing a binary search tree given an array of numbers. The algorithm has $O(N)$ time and $O(1)$ memory complexity if the given ar…