Build a plain binary search tree, and check whether it happens to obey the AVL rule.
What to build
A function that tests the AVL balance rule at every node of a tree.
Requirements
- Insert the keys into a plain binary search tree, with no rotations. The starter does this.
- Print
height H, whereHis the number of levels. - Print
balancedif every node's balance factor is -1, 0 or +1, andnot balancedotherwise.
Input
The first line has n. The second line has n different keys.
Output
Two lines.
Constraints
1 ≤ n ≤ 100.
Example
Input:
3
2 1 3
Output:
height 2
balanced
Why it works
The AVL rule is about every node, not only the root. A tree can look even at the top and still hide a long chain lower down, so the check has to recurse into both subtrees.
Examples
Example 1 · Input
3 2 1 3
Expected output
height 2 balanced
Example 2 · Input
3 1 2 3
Expected output
height 3 not balanced
Hints
Hint 1
The balance factor of a node is height(left) - height(right).
Hint 2
A tree is balanced when the factor at this node is -1, 0 or 1, and both of its subtrees are balanced too.
Hint 3
An empty tree is balanced.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct tree {
int key;
struct tree *left, *right;
} Tree;
Tree *insert(Tree *t, int key) {
if (t == NULL) {
Tree *n = malloc(sizeof(Tree));
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
if (key < t->key) t->left = insert(t->left, key);
else if (key > t->key) t->right = insert(t->right, key);
return t;
}
int height(Tree *t) {
if (t == NULL) return 0;
int l = height(t->left), r = height(t->right);
return 1 + (l > r ? l : r);
}
int balanced(Tree *t) {
if (t == NULL) return 1;
int b = height(t->left) - height(t->right);
if (b < -1 || b > 1) return 0;
return balanced(t->left) && balanced(t->right);
}
void free_tree(Tree *t) {
if (t == NULL) return;
free_tree(t->left);
free_tree(t->right);
free(t);
}
int main(void) {
int n;
scanf("%d", &n);
Tree *root = NULL;
for (int i = 0; i < n; i++) {
int key;
scanf("%d", &key);
root = insert(root, key);
}
printf("height %d\n", height(root));
if (balanced(root)) printf("balanced\n");
else printf("not balanced\n");
free_tree(root);
return 0;
}