-
Notifications
You must be signed in to change notification settings - Fork 0
/
16-binary_tree_is_perfect.c
87 lines (70 loc) · 1.8 KB
/
16-binary_tree_is_perfect.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include "binary_trees.h"
/**
* binary_tree_height - measures the height of a binary tree
* @tree: pointer to the root node of the tree to measure the height
*
* Return: height or 0 if tree is NULL
*/
size_t binary_tree_height(const binary_tree_t *tree)
{
size_t lheight, rheight;
if (!tree || (!tree->left && !tree->right))
return (0);
lheight = binary_tree_height(tree->left);
rheight = binary_tree_height(tree->right);
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
/**
* binary_tree_depth - measures the depth of a node in a binary tree
* @tree: Pointer to the node to measure the depth
*
* Return: The depth or 0 if tree is NULL
*/
size_t binary_tree_depth(const binary_tree_t *tree)
{
if (!tree)
return (0);
if (!tree->parent)
return (0);
return (1 + binary_tree_depth(tree->parent));
}
/**
* binary_tree_is_perfect_helper - helps to check if a binary tree is perfect
* @tree: Pointer to the root node
* @height: The height of the tree
*
* Return: 1 if it's perfect, 0 otherwise
*/
int binary_tree_is_perfect_helper(const binary_tree_t *tree, size_t height)
{
size_t depth;
if ((!tree->left && !tree->right))
{
depth = binary_tree_depth(tree);
if (depth == height)
return (1);
else
return (0);
}
if (!tree->left || !tree->right)
return (0);
return (binary_tree_is_perfect_helper(tree->left, height)
&& binary_tree_is_perfect_helper(tree->right, height));
}
/**
* binary_tree_is_perfect - checks if a binary tree is perfect
* @tree: Pointer to the root node of the tree to check
*
* Return: 1 if perfect or 0 if not perfect or tree is NULL
*/
int binary_tree_is_perfect(const binary_tree_t *tree)
{
size_t height;
if (!tree)
return (0);
height = binary_tree_height(tree);
return (binary_tree_is_perfect_helper(tree, height));
}