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:])
)
```

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.

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();
}
}
```

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.

Similar Questions

how can I build a balanced quad tree. Thanks, Marcos

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers i

I am implementing a binary search tree in C++11. I want to add a feature that makes it possible to mark different versions of the data structure with constant time complexity. What I thought about was

I'm trying to build a binary tree from In-order and Pre-order. Each node holds an integer value for data. I ran into a problem when having these arrays: Pre-order: 3,9,2,6,1,1,1,4 In-Order: 2,9,3,1,1

Is there a module for AVL or Red-Black or some other type of a balanced binary tree in the standard library of Python? I have tried to find one, but unsuccessfully (I'm relatively new to Python).

I have implemented a binary search tree and I want to add more functionality in its insertion function to make it a self-balancing tree. I am coding in C#. Can anybody please suggest me good tutorials

I need to create a function that creates a BST from an array, in python. The array is already sorted. The example is: function array_to_binary_search_tree(array, start, end) if start > end Return a

The function should takes a list xs and constructs a balanced binary search tree consisting of exactly the same set of elements as xs. The result should be like this: (if the list is [1,2,3,4,5,6,7,8]

I'm trying to write code for a binary search tree, the first method I'm working on is the add (insert) method. The root seems to insert properly, but I'm getting null pointer exception when adding the

Im trying to create an insertion function on an binary search tree. I looked at other questions here but they re not like my problem. I can compile it but it crashes on the commented line below: void

I am building a binary search tree. Here is the code: #include<stdio.h> #include<stdlib.h> struct tree_node { int val; struct tree_node *left; struct tree_node *right; }; void insert(struc

so I need to write a function in c++ that returns the depth of the tree. Im a bit confussed as to what this entails. It is the depth of each individual node or is it the depth of the entire tree for e

I want to implement a generic type binary search tree. The declarations are as follow: public BTNode<T> {} public class BinaryTree<T extends Comparable<T>> {} public class BinarySear

I have a binary tree of node containing an integer and a char. I'm working on Huffman Coding and I want to get the binary presentation of the nodes. A '0' is appended to the string for every left bran

Given an arbitrary set of values V and building a tree by inserting values left to right, what does it mean if I'm asked if my orderings of these values (to construct a minimum height and maximum heig

If each node in a binary search tree stores its weight (number of nodes in its subtree), what would be an efficient method to compute a rank of a given node (its index in the sorted list) as I search

I'm currently having difficulty inserting a node into a binary tree using recursion. I've been dwelling on this problem for a few days now and thought it was time I came looking for answers! Node clas

How wil you convert Binary Tree to Binary Search Tree with O(1) extra space ?

I have a homework assignment to implement a binary search tree (create, delete, search). I used the example provided by the teacher but I can't make it work. Here's my code so far: void insert_node(in

This question already has an answer here: Binary search tree insertion - root always null 1 answer I am making a basic binary search tree and its operations. Why isn't my insert working? It is

I'm being asked to display a binary search tree in sorted order. The nodes of the tree contain strings. I'm not exactly sure what the best way is to attack this problem. Should I be traversing the tre

I'm looking for a built-in Binary Search Tree implementation in .NET 4. Is there one?

This is my program, but I don't know how to show the binary search tree results in array (one dimensional). I use random as inputs. How to show binary search tree results in arrays? Help me please. #i

I am newcomer to Scala. I'm trying to develop my own immutable binary search tree. Firstly, I developed a binary search tree that takes Int on its nodes. After that , I decided to develop generic bin

So I am working on some homework and I have to complete a size balanced binary tree heap implementation, and I'm having some trouble with my enqueue function. We were given some code to start with and

What is the complexity of building a balanced binary tree of size n from scratch? Node insertion is O(log n). However, as you go along, the cumulative time is O( (log 1) + (log 2) + ... + (log (n-1)

I have read that std map is implemented using binary search tree data structure. BST is a sequential data structure (like elements in an array) which stores elements in a BST node and maintains elemen

I was working on Binary Tree and want to figure out if is there any algorithm to shuffle the tree and to sort level wise? Say for example I have an array as follows: int[] values = new int[16] {1,2,3,

Im trying to build an array based, Binary Search Tree by following the algorithm at: http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif%3A:600%3A:388%3A%3A/sites/dl/free/0070131511/2532

I want to write the algorithm of Balanced Binary Search Tree with backtracking would you please guild me about it? I dont know how should I implement it. I dont want any code I need just explanation.

Maybe fast/simple Question. I have a a Binary Tree Implemented already, Then I was hoping to convert binary search tree into an array or at least print it out as if in an array. Where I am having trou

I am trying to write a remove from a binary tree function. I'm kinda lost so I'm trying to handle it case by case, starting with if the value I'm trying to remove is in the root of the BST. To test my

I am working on a binary search tree and i have been given an insertnode function that looks like void insertNode(Node **t, Node *n) { if(!(*t)) *t=n; else if((*t)->key<n->key)insertNode(&am

I'm looking for a data structure where each element in it has two keys. With one of them the structure is a BST and looking at the other one, data structure is a heap. With a little search, I found a

I am building a binary search tree. Now I am having a problem with adding a node to the tree. void BinaryTree::add(int value, Node* node) { if(!node) node = new Node(value); else if(node->key <

I've been trying to implement a bst, in C. I think I'm almost there, but in my add node function, I create a temporary node called current to store the current node which is visited in the tree. Then

Can anyone please explain the difference between binary tree and binary search tree with an example?

How do you compute the average height of a binary search tree when adding 1000 random ints? What is the average height?

What is the benefit of a binary search tree over a sorted array with binary search? Just with mathematical analysis I do not see a difference, so I assume there must be a difference in the low-level i

I need to find if the binary tree is a perfect binary tree, meaning that each node has 2 nodes except for the last level. These are the methods I have so far but it doesn't seem to be working and I'm

hi i have implemented a bst in mips and i need to print this tree. Each node has following four information its value parent's address left child's address right child's address i should print the t

I want to use a binary search tree. I know that python has support for dictionaries. But it is a hashmap implementation. I want to know if python has any standard binary search tree implementation whi

According to what explained in wiki I think dfs on a binary tree is the same one with preorder traversal root--left--right.(am i right?) But just did a little search and got this code, and the author

My program keeps breaking when I try to find the max of my remove function. What I'm trying to do is overwrite what the user wants to remove with the maximum of the left tree, then delete that node in

I've been working on my Binary search tree for a while and the functions seem to work but I'm running into the same problem I had when I had a linked list program assignment. My nodes don't seem to wa

I would like to know some complexities of binary search tree, I can't find complete information. I want to know complexities for this operations on a binary search tree 1) to add/insert an element 2)

I have a binary tree with the only condition that there is a single node in the deepest level. The nodes in the tree have the parent property (as well as left, right, data) Is it possible to determine

I am new on C++. My background is from PHP and C#. I implement Binary search tree in VC++ in Visual Studio 2005 All operations are fine, I am facing the problem with delete in one particular scenario,

My partner and I are implementing a Binary Search Tree for a Data Structures & Algorithms course. We are encountering issues with our add method. This code is shown below: public class BinarySearc

Which would take longer? print all items stored in a binary search tree in sorted order or print all items stored in a hash table in sorted order. It would take longer to print the items of a hash ta