Counting unival subtrees - Follow Up

Question

This code is a revised version of the implementation which asked for an advice on improvement. Original post here: Counting unival subtrees Credits to: [Deduplicator], [Reinderien], [Toby Speight], [chux].

The revised version was applied following changes:

1. Merge insertRight(), insertLeft() function into createNode function
2. free resources after use
3. used const if referenced memory address value is not altered.
4. fix isTreeUniv() into recursive version
5. get rid of globals

Revised code:

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

typedef struct stTree
{
    struct stTree *left;
    struct stTree *right;
    int value;
} stTree;

stTree* createNode(int value, stTree *leftNode, stTree *rightNode)
{
    stTree *node = malloc(sizeof *node);
    if (!node) abort();

    node->left = leftNode;
    node->right = rightNode;
    node->value = value;

    return node;
}

bool isUnivSubTimpl(const stTree *node, const stTree *parent, size_t *count)
{
    if (!node) return 1;    //node without child count as unival subT

    bool r = isUnivSubTimpl(node->left, node, count) &isUnivSubTimpl(node->right, node, count);
    *count += r;

    return (r &node->value == parent->value);
}

size_t countUnivSubT(const stTree *node)
{
    size_t count = 0;
    isUnivSubTimpl(node, node, &count);
    return count;
}

static stTree* findBottomLeft(stTree *node)
{
    while (node->left)
        node = node->left;
    return node;
}

bool freeTree(stTree *node)
{
    if (!node) return true;
    stTree *bottomLeft = findBottomLeft(node);

    while (node)
    {
        if (node->right)
        {
            bottomLeft->left = node->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }

        stTree *old = node;
        node = node->left;
        free(old);
    }
        return true;
}

int main(void)
{
    //build a tree
    stTree *rootNode =
        createNode(0,
            createNode(1, NULL, NULL),
            createNode(0,
                createNode(1,
                    createNode(1, NULL, NULL),
                    createNode(1, NULL, NULL)
               ),
                createNode(0, NULL, NULL)));

    printf("total universal subree: %u\n", countUnivSubT(rootNode));
    if (freeTree(rootNode))
        printf("memory released\n");

}

Answer 1

Good job - it's nice to see improvements from the reviews you've received.

I would recommend using logical && rather than bitwise & in the computation r &node->value == parent->value. Results should be the same, but programmers expect to see logical operators with boolean values.

The computation of r cannot use && as is, because the right-hand side does need to be evaluated for its side-effects, even when the left-hand side is false. I'd consider rewriting as separate expressions, so a future maintainer doesn't "correct" the & to &&:

bool l_un = isUnivSubTimpl(node->left, node, count);  /* updates *count */
bool r_un = isUnivSubTimpl(node->right, node, count); /* updates *count */
bool r = l_un && r_un;

Identifiers beginning with is are reserved for Standard Library extension, so I'd advise changing the name isUnivSubTimpl, particularly as it has external linkage.

It isn't clear to me why freeTree() returns a bool, as it only ever returns true.

Building the tree could be simplified a little with

stTree *createLeafNode(int value)
{
    return createNode(value, NULL, NULL);
}