Building a balanced binary search tree

Question

Hi!

Is there a method to build a balanced binary search tree?

Example:

1 2 3 4 5 6 7 8 9

       5
      / \
     3   etc
    / \
   2   4
  /
 1

I'm thinking there is a method to do this, without using the more complex self-balancing trees. Otherwise I can do it on my own, but someone probably have done this already :)

---

Thanks for the answers! This is the final python code:

def _buildTree(self, keys):
    if not keys:
        return None

    middle = len(keys) // 2

    return Node(
        key=keys[middle],
        left=self._buildTree(keys[:middle]),
        right=self._buildTree(keys[middle + 1:])
        )

Answer 1

This paper explains in detail:

Tree Rebalancing in Optimal Time and Space
http://www.eecs.umich.edu/~qstout/abs/CACM86.html

Also here:

One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm
http://penguin.ewu.edu/~trolfe/DSWpaper/

If you really want to do it on-the-fly, you need a self-balancing tree.

If you just want to build a simple tree, without having to go to the trouble of balancing it, just randomize the elements before inserting them into the tree.

Answer 2

For each subtree:

• Find the middle element of the subtree and put that at the top of the tree.
• Find all the elements before the middle element and use this algorithm recursively to get the left subtree.
• Find all the elements after the middle element and use this algorithm recursively to get the right subtree.

If you sort your elements first (as in your example) finding the middle element of a subtree can be done in constant time.

This is a simple algorithm for constructing a one-off balanced tree. It is not an algorithm for a self-balancing tree.

Here is some source code in C# that you can try for yourself:

public class Program
{
    class TreeNode
    {
        public int Value;
        public TreeNode Left;
        public TreeNode Right;
    }

    TreeNode constructBalancedTree(List<int> values, int min, int max)
    {
        if (min == max)
            return null;

        int median = min + (max - min) / 2;
        return new TreeNode
        {
            Value = values[median],
            Left = constructBalancedTree(values, min, median),
            Right = constructBalancedTree(values, median + 1, max)
        };
    }

    TreeNode constructBalancedTree(IEnumerable<int> values)
    {
        return constructBalancedTree(
            values.OrderBy(x => x).ToList(), 0, values.Count());
    }

    void Run()
    {
        TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9));
        // displayTree(balancedTree); // TODO: implement this!
    }

    static void Main(string[] args)
    {
        new Program().Run();
    }
}

Answer 3

Make the median of your data (or more precisely, the nearest element in your array to the median) the root of the tree. And so on recursively.