How to compare root to leaf paths in a binary tree

Question

I am trying to search all the root-to-leaf paths within a given red black tree. In particular, I was wanting to write a test that, given a rbt, will assert that every path has the same count of black nodes.

I was trying something like this with two global variables:

static int count = 0, path = -1;

int check_paths(tree_node t)
{
    if (t == NULL)
    {
        if (path == -1)
            path = count;
        else
            return (path == count);

        return 1;
    }

    if (t->black == 1) ++count;
    int x,y;
    x = check_paths(t->left);
    if (t->black == 1) --count;
    y = check_paths(t->right);

    return (x&&y);
}

however, I was having trouble with cases when there were red nodes to the right of black nodes in left branches since this would mean that the count was decremented more than it should be.

Is there a better way to search root-to-leaf paths and count the frequency of a particular value and then compare the counts somehow? Or alternatively, is there a completely different method for testing a rbt's balance if given one (i.e. it is already made but the correctness of it is uncertain)?

Doug Currie Doug Currie · Accepted Answer · 2012-09-23T00:18:13

Consider how to make a function that takes a (sub-)tree, and (a) returns its black height if balanced, or (b) returns a negative number otherwise.

The base case is an empty (sub-)tree; it simply returns 0.

The inductive case:

lh is the result of a recursive call on the left subtree
lr is the result of a recursive call on the right subtree

If lh == lr and they are positive, then return lh + 1 if black

Here's some untested code:

int check_paths (tree_node t)
{
    if (t == NULL)
    {
        return 0;
    }
    int lh = check_paths(t->left);
    int rh = check_paths(t->right);

    if (lh != rh || lh < 0)
    {
        return -1;
    }
    else if (t->black == 1)
    {
        return (lh + 1);
    }
    else
    {
        return (lh)
    }
}

How to compare root to leaf paths in a binary tree

1 Answers