#include <iostream>
using namespace std;
typedef struct bin_tree_node
{
int v;
struct bin_tree_node *left;
struct bin_tree_node *right;
}BTNode;
BTNode *create_bin_tree_node(int v)
{
BTNode *p = new BTNode;
if(p != NULL){
p->v = v;
p->left = NULL;
p->right = NULL;
}
return p;
}
void create_balanced_bin_tree(BTNode **root, int arr[], int start, int end)
{
if(start <= end){
int mid = (start + end + 1) / 2;
*root = create_bin_tree_node(arr[mid]);
create_balanced_bin_tree(&((*root)->left), arr, start, mid - 1);
create_balanced_bin_tree(&((*root)->right), arr, mid + 1, end);
}
}
void print_bin_tree(BTNode *root)
{
if(root != NULL){
cout << root->v;
print_bin_tree(root->left);
cout << endl;
print_bin_tree(root->right);
cout << endl;
}
}
int main(int argc, char* argv[])
{
int arr[30];
for(int i = 0; i < 30; i ++){
arr[i] = i;
}
BTNode *root = NULL;
create_balanced_bin_tree(&root, arr, 0, 29);
print_bin_tree(root);
return 0;
}
Output
15 7 3 1 0
2
5 4
6
11 9 8
10
13 12
14
23 19 17 16
18
21 20
22
27 25 24
26
29 28
Solution
1. Insert into the tree the middle element of the array.
2. Insert (into the left subtree) the left subarray elements
3. Insert (into the right subtree) the right subarray elements
4. Recurse
Problem
Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.