Binary tree

[deanhystad]

The median, not the mean. The median is the middle value. There will be close to an equal number of values left and right of the median. The mean doesn't have to be close to the middle at all. The mean of 1, 2, 3, 4, 5, 6, 7, 8, 9, 100000 is 10004.5. The median is 5.

That doesn't really balance the tree though. If the values are sorted end up with a funny shape like this:

Output:
   5
 /   \
1     6
 \      \
  2      7
   \       \
    3       8
      \       \
       4       9

You could comput the median again for values left and right of the top node. And repeat the process for the next level, and the next level and so on.
root = median(1, 2, 3, 4, 5, 6, 7, 8, 9(
root.left = median(1, 2, 3, 4)
root.right = median(6, 7, 8, 9)
root.left.left = 1
root.left.right = median(3, 4)
root.left.right.right = 4
root.right.left = 6
root.right.right = median(8, 9)
root.right.right.right =

Output:
       5
     /   \
    /      \
   2        7
  /  \     /  \
 1    3   6     8
        \         \
         4         9

What you want to is a way to balance the tree after it is created. This allows adding nodes to the tree after you create it and then re-balancing the tree. It is a challenging problem, but there are lots articles about how to balance a binary tree.