cbinary-treedepth

Check if the number of nodes at any depth of the binary tree is equal to the height of the tree


I'm trying to do a function that checks if the number of nodes at any depth of the binary tree is equal to the height of the tree. Here's the code:

#include <stdio.h>
#include <stdlib.h>

/* STRUCTURE */

/* Structure of a binary tree */
typedef struct el {
    int info;
    struct el *left;    //Left child
    struct el *right;   //Right child
} node;

typedef node    *TREE;

/* Function that creates a binary tree */
TREE create_node(int x) {
    /* Allocates the node in the heap */
    TREE new = malloc(sizeof(node));

    new -> info = x;
    new -> left = NULL;
    new -> right = NULL;

    return new;
}

/* Function that finds the height of a binary tree */
int tree_height(TREE t) {
    /* If the tree is empty */
    if (t == NULL) {
        return 0;
    }

    /* Checks the subtrees */
    int left_height = tree_height(t -> left);
    int right_height = tree_height(t -> right);

    return 1 + (left_height > right_height ? left_height : right_height);
}

/* Auxiliary function that helps count the number of nodes at a certain depth */
int count_nodes_at_depth(TREE t, int target_depth, int current_depth) {
    /* If the tree is empty */
    if (t == NULL) {
        return 0;
    }

    /* If we're at the desired depth */
    if (current_depth == target_depth) {
        return 1;
    }

    /* Checks the subtrees */
    return count_nodes_at_depth(t -> left, target_depth, current_depth + 1) + count_nodes_at_depth(t -> right, target_depth, current_depth + 1);
}

/* Main function that helps to verify if the number of nodes at any depth is the same as the tree height */
int check_depth_nodes_equal_height(TREE t) {
    /* Calcola l'altezza dell'albero */
    int altezza = tree_height(t);

    for (int depth = 0; depth < altezza; depth++) {
        int nodes_at_depth = count_nodes_at_depth(t, depth, 0);

        /* If the number of nodes isn't the same as the tree height */
        if (nodes_at_depth != altezza) {
            return 0;
        }
    }

    /* If the condition's true for any depth */
    return 1;
}

int main() {
    /* Create the tree */
    TREE root = create_node(1);
    root -> left = create_node(2);
    root -> right = create_node(3);
    root -> left -> left = create_node(4);
    root -> left -> right = create_node(5);
    root -> right -> left = create_node(6);
    root -> right -> right = create_node(7);

    /* Find the tree height */
    int altezza = tree_height(root);
    printf("The tree height is: %d\n\n", altezza);

    /* Call the function */
    if (check_depth_nodes_equal_height(root)) {
        printf("The number of nodes at any depth is the same as the tree height\n");
    }
    else {
        printf("The number of nodes at any depth is NOT the same as the tree height\n");
    }
}

The only two functions that give me trouble are count_nodes_at_depth and check_depth_nodes_equal_height, since no matter how I modify the binary in the main function, it always says that the number of nodes is not equal as the tree height

I've tried adding a counter in count_nodes_at_depth to keep track of the number of nodes in that certain depth, but it does not seem to change the result at all. I've also tried modifying the structure of the binary tree to see if it was exclusive to the case present in the main functions, but it does not make a difference.


Solution

  • Given that count_nodes_at_depth works, let's look at check_depth_nodes_equal_height:

    int check_depth_nodes_equal_height(TREE t) {
        /* Calcola l'altezza dell'albero */
        int altezza = tree_height(t);
    
        for (int depth = 0; depth < altezza; depth++) {
            int nodes_at_depth = count_nodes_at_depth(t, depth, 0);
     
            /* If the number of nodes isn't the same as the tree height */
            if (nodes_at_depth != altezza) {
                return 0;
            }
        }
    
        /* If the condition's true for any depth */
        return 1;
    }
    

    The logic of this function stops as soon as it finds a level of the tree where depth does not equal height. This does not match the description of the function, which claims to do the exact opposite and return true if it finds a match.

    As written your function will only return true if all levels satisfy this criteria, rather than any. The fix is fortunately straightforward.

    int check_depth_nodes_equal_height(TREE t) {
        int altezza = tree_height(t);
    
        for (int depth = 0; depth < altezza; depth++) {
            if (altezza == count_nodes_at_depth(t, depth, 0)) 
                return 1;
    
        return 0;
    }