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.