Checking two properties of a tree

Question

I have the following definition:

A green-blue tree is a binary tree that follows the following properties:

• Each green node has only blue descendants.
• Every path that goes from a node to a leaf has the same number of blue nodes.

This is an example of a green-blue tree:

For the first part, we can ensure that every node has only blue descendants in $O(n)$, being $n$ the number of nodes. The algorithm could be as follows:

bool descendants_condition(node):
    if node == nullptr: 
        return true
    if node.info == green;
        return descendants_condition(node->left) and 
               descendants_condition(node->right);
    else:
        return only_blue_nodes(node->left) and 
               only_blue_nodes(node->right);

For the second part, I'm trying to avoid checking every path from every node to the leafs. I have the following intuition:

• If a node is a leaf, the condition is satisfied
• If a node is not a leaf, we should have the same number of blue nodes in the right and in the left.

However, this is not enough for me, and I would like to see a proof of this condition.

Answer 1

This is not a proof for the statement (since the statement is incorrect if the tree is not balanced), but rather another way to think and solve the problem.

Notice that in any path from the root to a leaf, say $v_1,\dots, v_k$ we must have that the number of green nodes is at most $1$ (by the first property). Also, notice that the number of blue nodes in the path, is the depth of the leaf $v_k$ minus either one or zero, depending on whether there was a green node in that path.

So, in order to count the number of blue nodes in a path you have to do the following two things:

1. Write at every leaf its depth (can be done in $O(n)$)
2. Write at every leaf whether there was a green node in the path from the root to it (think about it, it also can be done in $O(n)$)

Then finally you go through all leaves, calculate the number of blue nodes using this information, and make sure all leaves have the same value of it.