Find balanced BST with max height

See more:

C

trees

binary

search

Hello all!

I am trying to figure out a way to search a BST for its balanced subtree with max height.

What I have tried:

I have so far been able to find methods to check the height of a tree and to check whether the tree is balanced. I'm having a hard time getting these to work to locate the BST with max height.

As per KarstenK's hint, I have modified my code to include pointers:

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

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;
}

The above seems to work fine. However, the following shot at getting the max-height BST fails:

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;
}

DisplayTree is a (rather long) function to present the tree graphically. The code runs without errors, however, I get an empty tree. I would appreciate any comments.