/
120-binary_tree_is_avl.c
71 lines (65 loc) · 1.52 KB
/
120-binary_tree_is_avl.c
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
59
60
61
62
63
64
65
66
67
68
69
70
71
#include "binary_trees.h"
/**
* binary_tree_height - Function that measures the height of a binary tree
* @tree: tree to go through
* Return: the height
*/
size_t binary_tree_height(const binary_tree_t *tree)
{
size_t l = 0;
size_t r = 0;
if (tree == NULL)
{
return (0);
}
else
{
if (tree)
{
l = tree->left ? 1 + binary_tree_height(tree->left) : 1;
r = tree->right ? 1 + binary_tree_height(tree->right) : 1;
}
return ((l > r) ? l : r);
}
}
/**
* bal_avl - Auxiliar function to compare each subtree if its AVL.
* @tree: node that point to the tree to check.
* @high: node that point to the higher node selected
* @lower: node that point to the lower node selected.
* Return: 1 if tree is AVL, 0 if not.
*/
int bal_avl(const binary_tree_t *tree, int lower, int high)
{
size_t height_l, height_r, balancer;
if (tree != NULL)
{
if (tree->n > high || tree->n < lower)
{
return (0);
}
height_l = binary_tree_height(tree->left);
height_r = binary_tree_height(tree->right);
balancer = height_l > height_r ? height_l - height_r : height_r - height_l;
if (balancer > 1)
{
return (0);
}
return (bal_avl(tree->left, lower, tree->n - 1) &&
bal_avl(tree->right, tree->n + 1, high));
}
return (1);
}
/**
* binary_tree_is_avl - checks if a binary tree is a valid AVL tree.
* @tree: node that point to the tree to check.
* Return: 1 if tree is AVL, 0 if not.
*/
int binary_tree_is_avl(const binary_tree_t *tree)
{
if (tree == NULL)
{
return (0);
}
return (bal_avl(tree, INT_MIN, INT_MAX));
}