Your wasting your breath if you're trying to explain binary search to me. You may as well be telling a fish how to swim. You can read the article I wrote about binary search on my website if you want to see barely half of what I know about it.
If my instinct is correct, the original poster is asking how to construct a
pre-balanced binary tree,
not implement a
self-balancing binary tree. In which case, your initial reply was not what he was looking for. Perhaps if you had pointed him at the Scapegoat self-banalcing tree technique (in which pre-balanced binary trees are used), then your post might have been more relevant. However I suppose the poster might be happy with either.
Do you understand the nature of the problem of constructing a pre-balanced binary tree. The problem itself is naturally doubly-recursive by nature. One of the recursive calls can be turned into a loop, but both cannot. To do it without recursion would require you to maintain an explicit stack, and that is where I draw the line at reducing a recursive functions into an iterative one. So yes you definitely want to use recursion for the technique brewbuck and I were describing!
Finally I shall contradict myself and state that yes there is a completely different way to do it purely iteratively that I'm not going to go into details of, because it is very unelegant and ultimately not worth considering.
Matty_Alan: The rounding doesn't matter. Whenever there is an even number of items at the split, the resulting tree will be equally balanced whichever of the middle two items you pick as the splitter. E.g. for four items
Code:
3 2
/ \ / \
2 4 1 3
/ \
1 4
