Create a balanced binary search tree from a stream of integers with known size

I have something like array with sorted, integer-like elements.

Size is known. Array elements must be accessed in order, else access is bit expensive.

I want to create binary search tree, from single pass over the array.

Is there a way to do so, without using self balanced trees such Red Black, AA or AVL tree?

Complexity of log(n) is preferable.

Solution

It is possible in linear time, which is the best you can hope for as O(𝑛) nodes need to be created.

You can calculate the height ℎ of the tree. That height ℎ is one less than the number of bits in the binary representation of 𝑛, or otherwise put, ℎ = ⌊log_₂𝑛⌋

You can also calculate the number of nodes in the bottom level, which is 𝑛─2^ℎ+1.

Then you start a DFS-like recursion (inorder traversal) and create the tree from the bottom up. When the bottom level has reached the number of nodes it needs, then make sure the recursion doesn't create more nodes at that level.

Here is an implementation in Python:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


class BST:
    def __init__(self, iterable, n):
        self.root = None
        if not n:
            return

        def dfs(depth):
            if depth > 0:
                left = dfs(depth - 1)
                value = next(iterable)
                right = dfs(depth - 1)
                return Node(value, left, right)
            if self.bottom_count > 0:  # still nodes to put at bottom level
                self.bottom_count -= 1
                return Node(next(iterable))
            return None  # bottom level needs no more nodes
            
        height = n.bit_length() - 1
        self.bottom_count = n - (1 << height) + 1
        self.root = dfs(height)

    def print(self):
        def printrec(node, indent=""):
            if node:
                printrec(node.right, indent + "  ")
                print(indent, node.value)
                printrec(node.left, indent + "  ")
                
        printrec(self.root)

# Example run with 6 values
tree = BST(iter(range(6)), 6)
tree.print()

This example prints the generated tree sideways (root at the left):