C++

Forum

 
Find balanced BST with max height

Zelazny (1)
Hi to all!

I am trying to get the hang of BSTs and I am wondering whether there is a universally accepted way of searching a BST for a balanced subtree with max height.

I have attempted to come up with a solution to the problem and ended up with the following C code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
  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;
}


The above work fine and my problem lies in the next function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
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 function to present the tree in a graphic form (too long to post here). The code runs without errors, however, I end up with an empty tree instead of balanced BST with max height. I would appreciate any hints as to where this went wrong.
Thomas1965 (4571)
Seems the same post as in http://www.dreamincode.net/forums/topic/404488-find-bst-with-max-height/

I think you have more chances to get help when you post all the code so that people can compile and run it.
Topic archived. No new replies allowed.