rebalance_tree.cpp

// rebalance binary tree

#include <algorithm>
using namespace std;

struct node {
    node * left;
    node * right;
    int value;
    node(int value=0) : value(value), left(0), right(0) {}
};

void inorder(node * root, int *i, int * buf) {
    if (!root) return;
    inorder(root->left, i, buf);
    buf[(*i)++] = root->value;
    inorder(root->right, i, buf);
}

node * make_bst(int * buf, int start, int end) {
    if (start>end) return 0;
    int mid = (start + end)/2;
    node * root = new node(buf[mid]);
    root->left = make_bst(buf, start, mid-1);
    root->right = make_bst(buf, mid+1, end);
    return root;
}

void dump(node * root, int indent = 0) {
    if (!root) return;
    printf("%*s%d\n", indent, "", root->value);
    dump(root->left, indent+1);
    dump(root->right, indent+1);
}

void main() {
    int a[]={1,2,3,4,6,7,9};
    const int n = 7;
    node nodes[n];
    for (int i=0; i<n; i++) { nodes[i].value=a[i]; nodes[i].right=i+1==n ? 0 : &nodes[i+1]; };
    dump(&nodes[0]);

    int k = 0;
    inorder(&nodes[0], &k, a);
    sort(a, a+n);
    node * root = make_bst(a, 0, n-1);
    dump(root);
}