I came up with some code for a simple binary tree. I want to balance it but I am having trouble figuring out how to do this.

My idea was to create a malloced array of pointers to nodes then qsort them and rebuild the tree from that. The problem with this is that (AFAIK) I will need to use recursion to get at all the nodes which makes it tricky to keep track of the array index to place to node.

Heres my code:

Anyone got any suggestions as to the best way to go about this?Code:#include <stdio.h> #include <stdlib.h> typedef struct node { struct node *left; struct node *right;1 int num; }Node; Node *CreateHeadNode(int num) // Creates a new tree { Node *head = malloc(sizeof(Node)); head->left = NULL; head->right = NULL; head->num = num; return head; } void AddNode(Node *head, int num) { Node *new_node = malloc(sizeof(Node)); new_node->left = NULL; new_node->right = NULL; new_node->num = num; Node *here = head; Node *next = (num < here->num)? here->left: here->right; while(next) { here = next; next = (num < here->num)? here->left: here->right; } //'here' will be the last node if(num < here->num) here->left = new_node; else here->right = new_node; } void PrintTree(Node *head) { printf("Node: %2d\tL:%p \tR:%p\n", head->num, head->left, head->right); if(head->left) PrintTree(head->left); if(head->right)PrintTree(head->right); } void TreeSize(Node *node, int *count) { (*count)++; if(node->left)TreeSize(node->left, count); if(node->right)TreeSize(node->right, count); } void BalanceTree(Node *head) { int size = 0; TreeSize(head, &size); Node **temp = malloc(size * sizeof(Node*)); // Stuck here free(temp); } int main() { Node *head = CreateHeadNode(10); AddNode(head, 15); AddNode(head, 12); AddNode(head, 18); AddNode(head, 11); AddNode(head, 1); AddNode(head, 6); PrintTree(head); int count = 0; TreeSize(head, &count); printf("Node Count: %d\n", count); return 0; }

Cheers.