# Balancing A Binary Tree

• 08-11-2008
mike_g
Balancing A Binary Tree
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:
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.
• 08-11-2008
noops
My idea when I was going to do this was to create a new tree and insert the nodes in such a way that the tree would be balanced.

So

1 2 3 4 5 6 7 8 9

Insert the middle number, 5, which creates two halves: 1 2 3 4 and 6 7 8 9

Now insert the middle of each halve, 3, 8 which also creates more halves 1 2 and 4 -- 6 7 and 9

Repeat.

Not sure if that made sense or if that results in a truly balanced binary tree.
• 08-11-2008
mike_g
Well thats basically what I was planning to do once had the address of all the nodes in a flat array. Maybe I'm missing something here but I cant see a simple way of going about this w/o first converting the tree to an array or list.
• 08-12-2008
rasta_freak
Somewhere i read that either you must "convert" tree to array to balance it, OR use self-balancing tree from start (and of course, insert/delete functions are a bit more complex then).

Example of self-balanced tree:
http://en.wikipedia.org/wiki/Red-black_tree
(I even heard kernel hackers are playing with this "toy" too)
• 08-12-2008
Prelude
>Somewhere i read that either you must "convert" tree to
>array to balance it, OR use self-balancing tree from start
That's not quite right. It's possible to globally balance a tree in-place without adding extra complexity to the base tree. One such algorithm is DSW.
• 08-12-2008
mike_g
Hey prelude, I managed to find your site again. The self balancing trees look cool, but I'll try get this version working first. Still not sure how I'll flatten it; guess maybe I should start with deleting nodes first and think about it later.