Thread: Find balanced BST with max height

Hello all!

I am trying to come up with the code to find the balanced BST with max height within a given BST. So far, I have some preliminaries:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct Tree {     int key;
    struct Tree *left;
    struct Tree *right;
} Tree;

Tree* InsertBST(Tree* t, int k)
{
    if (t == NULL) {
        Tree* w = (Tree*) malloc(sizeof(Tree));
        w->key = k;
        w->left = NULL;
        w->right = NULL;
        return w;
    }

    if (k <= t->key)
        t->left = InsertBST(t->left, k);
    else
        t->right = InsertBST(t->right, k);

    return t;
}

int max(int a, int b)
{
    if (a >= b)
        return a;
    else
        return b;
}

int height(Tree* t)
{
    if (t == NULL)
        return 0;

    return 1 + max(height(t->left), height(t->right));
}

int IsBalanced(Tree *t)
{
    int lheight;
    int rheight;

    if (t == NULL)
        return 1;

    lheight = height(t->left);
    rheight = height(t->right);

    if (abs(lheight-rheight) <= 1 &&
        IsBalanced(t->left) &&
        IsBalanced(t->right))
        return 1;

    return 0;
}

These work fine. The problem lies within the following function:

Code:

void MaxBalanced(Tree *t, Tree *maxBal, int *maxBal_height)
{
    int t_height;

    if (t == NULL)
        *maxBal_height += 0;

    if (IsBalanced(t) == 1){
        t_height = height(t);
        if (t_height >= *maxBal_height){
            maxBal = t;
            *maxBal_height = t_height;
        }
    }
    else{
        MaxBalanced(t->left, maxBal, maxBal_height);
        MaxBalanced(t->right, maxBal, maxBal_height);
    }
}

int main()
{
    int i;

    Tree* t = NULL;

    int j[20] = { 993, 591, 2, 4, 395, 97, 446, 38, 279, 587, 28, 50, 265, 502, 114, 493, 808, 716, 897, 987 };

    for (i = 0; i < 20; i++)
        t = InsertBST(t, j[i]);

    DisplayTree(t);

    Tree* maxBal = NULL;
    int maxBal_height = 0;
    MaxBalanced(t, maxBal, &maxBal_height);

    DisplayTree(maxBal);

    return 0;
}

The code runs without errors but I get an empty tree. DisplayTree is a funtion which allows to present the tree graphically (too long to post here). I would appreciate any hints as to what is wrong with this approach.

Also posted here, and here.

I also find this interesting:

I started out finding functions to get the height of a given tree and check whether it is balanced.

I guess "finding" code is much easier than writing it.

Jim

Originally Posted by jimblumberg

I guess "finding" code is much easier than writing it.

Jim

Not being proficient in C I have spent a fair amount of time trying to understand the code I have found. Also, I have put in considerable effort into writing my own functions and it is because of the fact that I hit a snag that I am asking help of more experienced programmers.

Originally Posted by stahta01

Try fixing these two lines of code.

Code:

if (t == NULL)
        *maxBal_height += 0;

If you do NOT see the problem describe in words what the second line does.

Tim S.

If I'm not mistaken, I can get rid of these two lines since they do nothing. I tested this on different trees of different size and it would seem to me that the function passes the correct maximum height of a balanced subtree via pointer. So, it is my suspicion that the logic behind my code is not completely wrong (even if it is not the most efficient solution).

Right now, it seems to me that what's off is my use of pointers in

Code:

maxBal = t;

Originally Posted by stahta01

The proper fix is this.

Code:

if (t == NULL)
        *maxBal_height = 0;

And the problem is what I already told you.


Tim S.

Thanks for the pointer-to-pointer structure suggestion. With that in mind, I rewrote the code:

Code:

void MaxBalanced(Tree *t, Tree **maxBal, int *maxBal_height)
{
    int t_height;

    if (IsBalanced(t) == 1){
        t_height = height(t);
        if (t_height > *maxBal_height){
            maxBal = &t;
            *maxBal_height = t_height;
        }
    }
    else{
        MaxBalanced(t->left, maxBal, maxBal_height);
        MaxBalanced(t->right, maxBal, maxBal_height);
    }
}

int main()
{
    int i;
    srand (time(NULL));

    Tree* t = NULL;

    for (i = 0; i < 20; i++)
        t = InsertBST(t, rand() % 1000);

    Tree** maxBal = NULL;
    int maxh = 0;
    MaxBalanced(t, maxBal, &maxh);
    PrintTreeRoot(*maxBal);
    printf("%d", maxh);
    DisplayTree(*maxBal);

    return 0;
}

I get the idea why a pointer to pointer might be the way to go. However, I am clearly still missing something since this executes with segfault.