Checking if a binary tree is perfect in C-CodePudding

I am writing a function to check whether a tree is a perfect binary tree and here is my code:

#include "binary_trees.h"

/**
 * binary_tree_is_perfect - checks if a binary tree is perfect
 * @tree: is a pointer to the root node of the tree to check
 *
 * Return: If the tree is perfect, it returns 1. Otherwise, it
 * returns 0.
 */
int binary_tree_is_perfect(const binary_tree_t *tree)
{
    int check, depth, level;

    if (tree == NULL)
        return (0);
    level = 0;
    depth  = find_depth_left(tree);
    check = isPerfect(tree, depth, level);
    return (check); 
}

/**
 * find_depth_left - finds the depth of the left most leaf
 * in a binary tree
 * @tree: is a pointer to the tree to measure the left most
 * depth
 *
 * Return: The depth of the left most node
 */
int find_depth_left(const binary_tree_t *tree)
{
    if (!tree->left)
        return (0);
    return (1   find_depth_left(tree->left));
}

/**
 * isPerfect - helper function to find if a binary tree is perfect
 * @depth: this is the left most depth of the tree
 * @level: this is the level where to the check is happening
 *
 * Return: If the tree is perfect, it returns 1. Otherwise, it
 * returns 0.
 */
int isPerfect(const binary_tree_t *tree, int depth, int level)
{
    if (!tree->left && !tree->right)
        return (depth == (level   1));  
    if (!tree->left || !tree->right)
        return (0);
    return (isPerfect(tree->left, depth, level   1) &&
            isPerfect(tree->right, depth, level   1));
}

My logic: I will find the left most leaf node of the tree (this is just my choice), then I will check whether the nodes will have two children or none with isPerfect function. But for every tree I input, I get 0 (meaning the tree is not perfect). This happens even if the tree is a perfect binary tree. Where did my logic go wrong?

CodePudding user response：

First the code was well thought out.

The internal (recursive) functions work on a non-null node. That would be fine for a OOP, object oriented programming, language, as then the function could be a member function on the node class binary_tree_t.

However here it led to difficulty: find_depth on a single node tree would logically be 1, not 0.

You could write it with accepting tree parameters as null. Then level and depth coincide.

bool binary_tree_is_perfect(const binary_tree_t *tree)
{
    int depth  = find_depth_left(tree);
    int level = 0;
    bool check = isPerfect(tree, depth, level);
    return check; 
}

int find_depth_left(const binary_tree_t *tree)
{
    if (!tree)
        return 0;
    return 1   find_depth_left(tree->left);
}

bool isPerfect(const binary_tree_t *tree, int depth, int level)
{
    if (!tree)
        return level == depth;
    if (!tree->left != !tree->right)
        return false;
    return isPerfect(tree->left, depth, level) &&
           isPerfect(tree->right, depth, level);
}

So it was a semantic (=in meanding) difference between level and depth. For the logic it would have been better to use one variable: expectedDepth.

bool binary_tree_is_perfect(const binary_tree_t *tree)
{
    int expectedDepth  = find_depth_left(tree);
    bool check = isPerfect(tree, expectedDepth);
    return check; 
}

int find_depth_left(const binary_tree_t *tree)
{
    return !tree ? 0 : 1   find_depth_left(tree->left);
}

bool isPerfect(const binary_tree_t *tree, int expectedDepth)
{
    if (!tree)
        return 0 == expectedDepth;
    if (!tree->left != !tree->right)
        return false;
    return expectedDepth >= 0 &&
           isPerfect(tree->left, exoectedDepth - 1l) &&
           isPerfect(tree->right, expectedDepth - 1);
}

expectedDepth >= 0 && is probably not needed as you took the expected depth from the left most leaf, as then the left subtree's isPerfect will return false. Interesting is it not?