Checking if a binary tree is perfect in C

Question

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?

Start with the simplest "perfect" tree you can create (basically a root node with two leaf nodes), and use a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through your code line by line while monitoring variables and their values, to see what really happens. To help with this I recommend you split up the recursive calls into two separate statements, and store their results in temporary variable. That makes it easier to step into the two separate calls. — Some programmer dude, Nov 16 '22 at 07:52

score 3 · Accepted Answer · answered Nov 16 '22 at 08:39

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?

Your answer is great, and I have understood, just one question. You have said that my functions work on non-null node, and that it would be fine if it was an OOP language, what do you mean by that? Excuse me if my question is not well-structured, I am a new programmer. — Leuel Asfaw, Nov 16 '22 at 12:04
The tree node would be something like `class Node { Node left, right; int depth() { int d = 1; if (left != null) d += left.depth(); ... return d; } }`. — Joop Eggen, Nov 16 '22 at 14:11

Checking if a binary tree is perfect in C

1 Answers1